Computer Science Colloquium
Time+Place : Sunday 19/06/2011 14:30 room 337-8 Taub  Bld.
Speaker    : Amit Sahai
Affiliation: UCLA
Host       : Yuval Ishai
Title      : Efficient and Explicit Coding for Interactive Communication
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
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
* 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
* 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.
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.
Visit our home page-   <>
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <> 
Announcement from: Hadas Heier   <>