Technion Computer Science Colloquium 19/06/2011 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 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. ---------------------------------------------------------- Visit our home page- <http://www.cs.technion.ac.il/~colloq> --------------------------------------------------------- Technion Math. Net (TECHMATH) Editor: Michael Cwikel <techm@math.technion.ac.il> Announcement from: Hadas Heier <heier@cs.technion.ac.il>