Prahladh Harsha, Rahul Jain, David McAllester, Jaikumar Radhakrishnan

We examine the communication required for generating random variables

remotely. One party Alice will be given a distribution D, and she

has to send a message to Bob, who is then required to generate a

value with distribution exactly D. Alice and Bob are allowed

to share random bits generated ...
more >>>

Gillat Kol, Ran Raz

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 ... more >>>