The Laureates

Copyright © Klaus Tschira Stiftung / Peter Badge

Madhu Sudan

Born 12 September 1966, Chennai, India

Nevanlinna Prize “for contributions to several areas of theoretical computer science, including probabilistically checkable proofs, nonapproximability of optimization problems, and error-correcting codes.”

Madhu Sudan studied Computer Sciences at the Indian Institute of Technology, New Delhi (Bachelor of Technology 1987) and subsequently received his doctorate from the University of California, Berkeley (Ph.D. 1992). His doctoral thesis was on “Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems” with Virkumar Umesh Vazirani as his adviser. While a graduate student he did research at the IBM Almaden Research Center (Summer 1990) and after his Ph.D. worked at the IBM Thomas J. Watson Research Center (1992-97). Sudan was made an associate professor at Massachusetts Institute of Technology (1997-2002), and became a professor there in 2003. Sudan has been the Fujitsu Chair Professor and Danny Lewin Outstanding Professor at MIT from 2005-2009. He also served as an associate director of the Computer Science and Artificial Intelligence Laboratory from 2007-2009. Sudan is currently a Principal Researcher at Microsoft Research New England and Adjunct Professor of Computer Science at MIT.
Madhu Sudan has received numerous awards and honours, including the Gödel Prize (2001) and a Guggenheim Fellowship (2005-06).

Sudan has made particularly important contributions in three areas: probabilistic checkable proofs; the non-approximability of solutions to combinatorial problems; and error correcting codes. The theory of probabilistically checkable proofs generalises the now standard classification of problems into complexity classes. It takes a fresh look at the question of how complex a problem is. Traditionally, this question has been studied by examining how a Turing machine – the theoretical model of a computer which was developed by the British mathematician Alan Turing in 1936 – solves a problem or checks the correctness of a proof. With probabilistic proof checking, this concept is generalized. A ‘verifier’ poses questions to a ‘prover’. The questions are asked over a certain number of rounds, and can be generated using chance among other things. The job of the prover – in principle a very powerful Turing machine – is to convince the verifier that the proof is correct. One can show that the class of problems that can be proved by this method is larger than the class of “hard” problems of computer science and mathematics known as NP. Together with colleagues, Sudan proved that the class NP in fact contains exactly those problems that can be solved even if the verifier checks only a small part (that is, a constant number of bits) of the proof he gets in each round from the prover, and that only a small number of rounds is necessary.

This proof surprised the expert community not least because it has another startling implication. Under certain assumptions one can show that there are problems that cannot be solved approximately by fast algorithms; they are in a sense really “hard”. This is interesting because it touches one of the core questions of computer science “Is P=NP?”, which asks if every problem in NP has a fast algorithm.