Newtonpedia ES
Home › Computing › Madhu Sudan
Madhu Sudan
Image: Wikimedia Commons

Madhu Sudan

Indian-American computer scientist known for work on computational complexity and error-correcting codes · 1966

Born
September 12, 1966
Country
United States, India
Section
Computing

Biography

Madhu Sudan (born 12 September 1966) is an Indian-American computer scientist whose research sits at the boundary between mathematics and theoretical computer science. Since 2015 he has been Gordon McKay Professor of Computer Science at the John A. Paulson School of Engineering and Applied Sciences at Harvard University. His work asks what computers can check, how reliably, and at what cost, and it has shaped how researchers design algorithms and communication systems that must work despite errors.

Sudan completed his bachelor's degree in computer science at IIT Delhi in 1987. He then moved to the United States for his doctorate at the University of California, Berkeley, which he received in 1992. His dissertation, Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems, addressed how one can verify a mathematical claim without examining every step, a question that remained central to his later career.

From 1992 to 1997 he was a research staff member at the IBM Thomas J. Watson Research Center in Yorktown Heights, New York. He then became a researcher at the Massachusetts Institute of Technology (MIT). From 2009 to 2015 he was a permanent researcher at Microsoft Research New England, before joining the Harvard faculty. Over these years he worked with many collaborators across several leading centres of theoretical computing.

His best-known contribution concerns probabilistically checkable proofs, a way of rewriting a mathematical proof so that a computer can check it by inspecting only a few randomly chosen parts. If the proof is correct, the machine accepts it; if it contains mistakes, the machine is very likely to catch them without reading the whole thing. This idea, developed with colleagues of his generation, connects to results on how hard it is to approximate solutions of optimisation problems, that is, to find answers that are nearly best when the exact one is out of reach. Sudan also worked on error-correcting codes, which add redundant information to a message so it can be recovered even if part of it is corrupted, and on list decoding, which allows a decoder to return several plausible answers when the received data is very noisy.

His work earned major recognition: the Sloan Research Fellowship in 1998, the Rolf Nevanlinna Prize at the International Congress of Mathematicians in 2002, which honours mathematical work in computer science, and the Gödel Prize in 2001, shared for the work on probabilistically checkable proofs. The same work brought him the ACM Distinguished Doctoral Dissertation Award in 1993. He has been a Fellow of the ACM since 2008, a fellow of the American Mathematical Society since 2012, and was elected to the US National Academy of Sciences in 2017. In 2021 he was awarded the IEEE Richard W. Hamming Medal for 2022.

Sudan's legacy lies in linking the theory of mathematical proof with the practice of computing, showing that verification can be done very efficiently. His ideas on approximating hard problems and decoding codes remain part of the training of anyone who studies algorithms and digital communication.

Main contributions

  • 1992Doctoral dissertation on efficient checking of polynomials and proofs, at the University of California, Berkeley.
  • 2001Gödel Prize, for his work on probabilistically checkable proofs.
  • 2002Rolf Nevanlinna Prize, for his work on the mathematical aspects of computer science.
  • 2022IEEE Richard W. Hamming Medal, awarded in 2021 for 2022.
  • Development of probabilistically checkable proofs, which allow a proof to be verified by reading only a few randomly chosen parts.
  • Work on the non-approximability of optimisation problems, that is, on the limits of finding nearly optimal solutions.
  • Contributions to error-correcting codes and list decoding.

Teachers and students

Studied under:

Taught:

Benjamin RossmanYevgeniy DodisPrahladh HarshaAdam D. SmithRyan William O'DonnellMikhail V. AlekhnovitchVenkatesan GuruswamiApril Rasala LehmanSergey YekhaninElena GrigorescuBrendan A. JubaSwastik KoppartyVictor ChenEric LehmanShubhangi SarafAlan Xinyu GuoMohammad BavarianBadih Ghazi

See their academic family tree →

Their contemporaries

While Madhu Sudan was alive (1966–)…

Alive at the same time

Discovered or invented in those years

  • 1969
    InternetA global network of interconnected computer networks that communicate using the TCP/IP protocol suite.
  • 1971
    EmailA network service that lets users send and receive digital messages through addressed mailboxes, much like postal mail but electronic.
  • 1973
    Mobile phoneA handheld wireless phone that lets people make and receive calls while moving across a cellular network area.
  • 1975
    Global warmingThe long-term rise in Earth's average surface temperature, driven mainly by greenhouse gases released through human activity.
  • 1989
    World Wide WebA system of linked documents and resources, connected by hyperlinks and accessed over the Internet with web browsers.
  • 1990
    Web browserA program that lets people access the web by fetching a page's files from a server and displaying them on screen as an interactive page.

See this life on the timeline →

More people in Computing