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