Back
Mathematical Sciences

Madhu Sudan

Principal Researcher, Microsoft Research New England, and Adjunct Professor, Electrical Engineering and Computer Science department, and Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, USA

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

1987-1992

1987-1992

B.Tech. (Computer Science and Engineering), IIT-Delhi; Ph.D., University of California, Berkeley

1994

1994

Starts postdoctoral research at University of Chicago

1992

1992

Joins IBM Thomas J. Watson Research Center Mathematical Sciences Department as Research Staff Member

1997

1997

Appointed Associate Professor in the Department of Electrical Engineering and Computer Science at Massachussetts Institute of Technology

1998

1998

Wins the Sloan Fellowship

2001

2001

Wins the Godel Prize

2003

2003

Appointed Professor at MIT EECS

2005

2005

Appointed Fujitsu Chair Chair Professor at MIT EECS

2009

2009

Appointed Principal Researcher at Microsoft Research

2014

2014

Wins Infosys Prize in Mathematical Sciences

2015

2015

Appointed Gordon McKay Professor at Harvard SEAS

2017

2017

Elected as Member, National Academy of Sciences

1987-1992
1992
1997
1998
2001
2003
2005
2009
2014
2015
2017

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.

Prof. Sunita Sarawagi

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.

Srinivasa S. R. Varadhan

Jury Chair
Mathematical Sciences