Abstract:

In this work, we study the fundamental problem of reliable interactive
communication over a noisy channel.  In a breakthrough sequence of
papers published in 1992 and 1993, Schulman gave non-constructive
proofs of the existence of general methods to emulate any two-party
interactive protocol such that: (1) the emulation protocol only takes
a constant-factor longer than the original protocol, and (2) if the
emulation protocol is executed over any discrete memoryless noisy
channel with constant capacity, then the probability that the
emulation protocol fails to perfectly emulate the original protocol is
exponentially small in the total length of the protocol.
Unfortunately, Schulman's emulation procedures either only work in a
nonstandard model with a large amount of shared randomness, or are
non-constructive in that they rely on the existence of absolute tree
codes. The only known proofs of the existence of absolute tree codes
are non-constructive, and finding an explicit construction remains an
important open problem. Indeed, randomly generated tree codes are not
absolute tree codes with overwhelming probability.

In this work, we revisit the problem of reliable interactive
communication, and obtain the first fully explicit (randomized)
efficient constant-rate emulation procedure for reliable interactive
communication.  Our protocol works for any discrete memoryless noisy
channel with constant capacity, and our protocol's probability of
failure is exponentially small in the total length of the protocol. We
accomplish this goal by obtaining the following results:

* We introduce a new notion of goodness for a tree code, and define
the notion of a potent tree code.  We believe that this notion is of
independent interest.
* We prove the correctness of an explicit emulation procedure based on
any potent tree code.  (This replaces the need for absolute tree codes
in the work of Schulman.)
* We show that a randomly generated tree code (with suitable constant
alphabet size) is an efficiently decodable potent tree code with
overwhelming probability.  Furthermore we are able to partially
derandomize this result by means of epsilon-biased distributions using
only $O(n)$ random bits, where $n$ is the depth of the tree.

These (derandomized) results allow us to obtain our main result. Our
results also extend to the case of interactive multi-party
communication.

This talk is based on joint work with Ran Gelles and joint work with
Ran Gelles and Ankur Moitra.


SHORT BIO:
Professor Amit Sahai received his Ph.D. in Computer Science from MIT
in 2000. From 2000 to 2004, he was on the faculty at Princeton
University; in 2004 he joined UCLA, where he currently holds the
position of Professor of Computer Science. His research interests are
in security and cryptography, and theoretical computer science more
broadly. He has published more than 80 original technical research
papers at venues such as the ACM Symposium on Theory of Computing
(STOC), CRYPTO, and the Journal of the ACM. He has given a number of
invited talks at institutions such as MIT, Stanford, and Berkeley,
including the 2004 Distinguished Cryptographer Lecture Series at NTT
Labs, Japan. Professor Sahai is the recipient of numerous honors; he
was named an Alfred P. Sloan Foundation Research Fellow in 2002,
received an Okawa Research Award in 2007, and a Google Faculty
Research Award in 2010. His research has been covered by several news
agencies including the BBC World Service.