2002/12/01 by Shafi Goldwasser
Computer Science · #cs.CC
published as Proceedings of the ICM, Beijing 2002, vol. 1, 105--115
arxiv created 2002/12/01 · arxiv updated 2009/12/01
Madhu Sudan's work spans many areas of computer science theory including computational complexity theory, the design of efficient algorithms, algorithmic coding theory, and the theory of program checking and correcting. Two results of Sudan stand out in the impact they have had on the mathematics of computation. The first work shows a probabilistic characterization of the class NP -- those sets for which short and easily checkable proofs of membership exist, and demonstrates consequences of this characterization to classifying the complexity of approximation problems. The second work shows a polynomial time algorithm for list decoding the Reed Solomon error correcting codes. This short note will be devoted to describing Sudan's work on probabilistically checkable proofs -- the so called \it PCP theorem and its implications.