Login
Computer Science @ Rochester
Monday, November 21, 2011
11:00 AM
Computer Studies Bldg. 209
Atri Rudra
University of Buffalo
List Decoding: The Master of Disguise
Suppose you want to communicate over a point-to-point noisy channel. If the noise is adversarial, then a classical observation due to Hamming states that one can only correct up to half the information-theoretically possible number of error if one wants to *uniquely* recover the transmitted information. However, if one is allowed to output a small list of possibilities, then one can indeed recover from information-theoretically optimal number of error. "List decoding" thus holds the promise of optimal communication even in the presence of *worst-case* errors.

In its most obvious avatar, list decoding has applications in communication. On the other hand, theoretical computer scientists have found solutions to problems, which on the surface have nothing to do with communication but use list decoding under different guises. Most of these applications are in complexity theory.

This talk will first motivate list decoding and then give a quick tour of the progress on efficient list decoding algorithms in the past decade and a half. Then the talk will focus on two new (somewhat more practical but still somewhat surprising) applications of list decoding. In particular, we will see how list decoding can lead to sub-linear time algorithms for compressive sensing (which has applications in signal and image processing among others) and group testing (which has applications in biology among others). Finally, we will see how list decoding can prove that some existing hash functions are more powerful than previously thought, which leads to some applications in cloud security. The latter result also uses another staple of complexity theory-- Kolmogorov complexity.

The talk will be self-contained and is based on joint works with Mohammad "Ifte" Husain (UB), Piotr Indyk (MIT), Steve Ko (UB), Hung Ngo (UB), Ely Porat (Bar-Ilan), Ram Sridhar (UB) and Steve Uurtamo (Groupon/UB).

Bio: Atri Rudra is an Assistant Professor of Computer Science and Engineering at University at Buffalo, State University of New York, Buffalo. Atri received his Bachelor's degree from Indian Institute of Technology, Kharagpur, India in 2000 and his Ph.D. from University of Washington in 2007. From 2000-2002, he was a Research Staff Member at IBM India Research Lab, New Delhi, India.

His research interests lie in theoretical computer science and in particular, theory of error-correcting codes, data stream and sub-linear algorithms, game theory and algorithmic mechanism design, approximation algorithms, computational complexity, finite field theory and applications. He is a recipient of an NSF CAREER award (2009), HP Labs Innovation Research Award (2010), ESA best paper award (2010) and the UB Exceptional Scholars - Young Investigator award (2011).

Refreshments will be provided at 10:45