Interactive Channel Capacity

Speaker: Ran Raz (Weizmann Institute)

Few papers in the history of science have affected the way that people think in so many branches of science, as profoundly as Shannon's 1948 paper "A Mathematical Theory of Communication.'' One of the gems in that paper is an exact formula for the channel capacity of any communication channel. For example, for the binary symmetric channel with noise rate $\epsilon$, the channel capacity is $1-H(\epsilon)$, where $H$ denotes the binary entropy function. This means that one can reliably communicate $n$ bits, with a negligible probability of error, by sending roughly
$n/(1-H(\epsilon))$ bits over the channel.

We study the interactive channel capacity of an $\epsilon$-noisy channel. The interactive channel capacity $C(\epsilon)$ is defined as the minimal ratio between the communication complexity of a problem (over a non-noisy channel), and the communication complexity of the same problem over the binary symmetric channel with noise rate $\epsilon$, where the communication complexity tends to infinity.

Our main result is the upper bound $C(\epsilon) \leq 1-\Omega(\sqrt{H(\epsilon)})$. This compares with Shannon's non-interactive channel capacity of $1-H(\epsilon)$. In particular, for a small enough $\epsilon$, our result gives the first separation between interactive and non-interactive channel capacity, answering an open problem by Schulman (1992).

We complement this result by the lower bound $C(\epsilon) \geq 1-O(\sqrt{H(\epsilon)}),$ proved for the case where the players take alternating turns.

This is joint work with Gillat Kol.

Candidate Weak Pseudorandom Functions in AC0 o MOD2

Speaker: Andrej Bogdanov (Chinese University of Hong Kong)

Pseudorandom functions (PRFs) play a fundamental role in symmetric-key cryptography. However they are inherently sequential: Razborov and Rudich showed that PRFs cannot be implemented in the class AC0(MOD2). Weak pseudorandom functions (weak PRFs) do not suffer from this complexity limitation, yet they suffice for many cryptographic applications.

We study the minimal complexity requirements for constructing weak PRFs. To this end, we present a candidate construction of a weak PRF in the class AC0 o MOD2. We show that functions our PRF is inapproximable by GF(2) polynomials of low degree and has negligible correlation with any fixed Boolean function family of subexponential size.

We also initiate a study of the class AC0 o MOD2 that captures the complexity of our construction. We conjecture that all functions in this class have a Fourier coefficient of magnitude exp(−polylogn) and prove this conjecture in two cases: (1) when the AC0 function is a DNF and (2) when the MOD2 function is typical.

This talk is based on joint work with Adi Akavia, Siyao Guo, Akshay Kamath and Alon Rosen.