Speaker: Prof. Haim Permuter (Ben Gurion University)

Title: Toward single letter feedback capacity via structured auxiliary random variable

Abstract:

It is well known that feedback capacity is characterized using directed information which is a multi-letter expression. In this talk we aim to convert the multi-letter expression into a single-letter expression using a new idea of an auxiliary random variable that has a graphical structure.

Auxiliary random variables (r.v.) play a fundamental role in characterizing the capacity of channels, especially in multi-user setting such as Gelfand-Pinsker or the degraded broadcast channel. In most cases, choosing a sequence of an i.i.d auxiliary r.v. allows us to simplify a capacity expression and to have a computable, single-letter form. In this talk we will introduce a new kind of auxiliary r.v. that is not i.i.d. but has memory that is generated on a graphical structure. In particular, we show that the feedback capacity of the unifilar channel is upper bounded by a single-letter expression that is a function of the stationary distribution on the graph representing the memory of the auxiliary r.v.. Furthermore, in all cases where the capacity is known, such as the trapdoor channel, Ising channel, Dicode channel, erasure channel with no repeated ones, the upper bound yields, with a small cardinality bound on the structured auxiliary r.v., a tight bound on the feedback capacity.

As time permits, we will also introduce a sufficient condition on having a specific structured auxiliary that admits the feedback capacity, and present an achievability scheme for channels with memory based on the posterior matching idea.

Bio:

Haim Permuter received his B.Sc. (summa cum laude) from Ben-Gurion University (BGU) and Ph.D. from Stanford University, both in in Electrical Engineering, in 1997 and 2008, respectively. Between 1997-2004, he served as a scientific research officer in an R&D unit in the Israeli Defense Forces. In summer 2002 he worked for IBM, Almaden research center. He is a recipient of several rewards including Eshkol Fellowship, Wolf Award, Fulbright Fellowship, Stanford Graduate Fellowship, Allon Fellowship and the prestigious ERC grant from the Eropean Union for 2013-2018. Haim serves as an associate editor of the IEEE transaction on Information Thoery. Haim joined the faculty of Electrical Engineering Department at BGU in Oct 2008, and is now an associate professor.