Madhu Sudan
Biography
Considered one of the leading researchers in theoretical computer science, Madhu Sudan's influential work on the development of probabilistically checkable proof (PCP) systems and role in proving the PCP theorem spurred a revolution in understanding the ability to efficiently approximate solutions of optimization problems. The PCP theorem is perhaps the most important and influential development in computational complexity since the discovery of nondeterministic polynomial (NP)-completeness over 50 years ago. It has had important impact, both theoretical (in computational learning, circuit complexity, and coding theory) and also practical, as PCPs now find their ways into blockchain and cloud computing technologies. PCPs allow super-fast verification by probing the purported proof at very few random locations. For every valid statement there exists a valid proof that is always accepted by the verification procedure, whereas for a nonvalid statement each false proof is rejected with probability of at least one-half (taken over the coin tosses of the verification procedure). The main result is that any standard proof system can be efficiently transformed into a PCP proof system that can be verified by probing a constant (independent of the original proof) number of locations. Sudan has also made fundamental contributions to the study of list decoding of various codes, including the Reed-Solomon code, and to the application of these ideas in the context of hardness amplification. His work on the Reed-Solomon list-decoding algorithm has changed the way to think about decoding, where it used to be an unknown and esoteric concept. That possibly the most famous and important code has an elegant and efficient list-decoding algorithm is now a basic fact that is required knowledge of all graduate students in theoretic computer science. List decoding has proved very influential with applications in cryptography and the study of the role of randomness in computational complexity.
An IEEE Fellow and recipient of the Nevanlinna Prize from the International Mathematical Union, Sudan is a Gordon McKay Professor with the John A. Paulson School of Engineering and Applied Sciences at Harvard University, Cambridge, MA, USA.
