The Infosys Prize 2014 in Mathematical Sciences is awarded to Prof. Madhu Sudan for his seminal contributions to theoretical computer science, especially in the areas of Probabilistically Checkable Proofs (PCP) and error‑correcting codes.
Infographic:
Correcting Errors In Data And Logic
Scope and Impact of Work
The central theme of Prof. Madhu Sudan's work is how to efficiently extract useful information from data that has errors. This theme has wide‑ranging applications : from theoretical (e.g., how to verify a proof) to practical (e.g., how to recover correct data stored on a CD when it gets scratched).
His contributions have led to the development of a new way of writing proofs, called Probabilistically Checkable Proofs (PCP), whose correctness can be verified with high probability by checking them at very few locations. This result, famously known as the PCP Theorem, has been hailed as one of the most fundamental contributions of theoretical computer science, and is closely tied to proving inapproximability of several NP-hard (Non-deterministic Polynomial-time hard) problems. His subsequent work has had a fundamental impact on our understanding of PCPs.
Sudan's work on list decoding opened up the possibility of correcting a far larger number of errors in data than was previously thought possible. This brought a new vigor to the field of error-correcting codes, and has led to many more advances in this field.
Bio
Prof. Madhu Sudan has been a Principal Researcher at Microsoft Research New England since 2009. He received his B.Tech. in Computer Science and Engineering from IIT-Delhi in 1987 and his Ph.D. from the University of California, Berkeley, in 1992. From 1992 to 1997, he was at the IBM Thomas J. Watson Research Center, after which he moved to MIT as a faculty member in the Electrical Engineering and Computer Science (EECS) department and a member of their Computer Science and Artificial Intelligence Laboratory (CSAIL). Sudan's current research interests lie in the interface of Computation and Communication, and in particular, in the role of errors in this interface. He has made important contributions to theoretical computer science in areas such as probabilistically checkable proofs, non-approximability of optimization problems, list decoding, and error‑correcting codes.
During his distinguished career, he has won many awards, including the ACM Distinguished Doctoral Dissertation (1993), the Godel Prize (2001), and the Rolf Nevanlinna Prize (2002). He is a fellow of ACM and the American Mathematical Society.
Timeline
Jury Citation
Prof. Madhu Sudan has made seminal contributions in the domains of Probabilistically Checkable Proofs (PCP) and error‑correcting codes. He was one of the authors of the famous PCP Theorem, proving that any proof can be efficiently converted to a form such that one can conclude with high probability that the proof is correct by looking at only a few locations of the proof. His algorithm for list decoding of Reed-Solomon codes was a major breakthrough that found applications in diverse areas. In a career spanning 25 years, Prof. Sudan has established himself as one of the leaders in theoretical computer science.
Madhu Sudan reacts to winning the Infosys Prize
Congratulations Madhu. The jury was quite impressed by your work over the years covering different areas of theoretical computer science. Probabilistic proof checking is an important tool in the verification of algorithms making sure that programs work correctly and do what they are supposed to do. Your work in coding has resulted in better error-correcting codes that significantly impacts electronic communication and encryption. The panel is very glad to turn to theoretical computer science and choose you as the recipient. Congratulations.
