Madhu Sudan

Fujitsu Professor of Electrical Engineering, Principal Researcher, Microsoft Research New England. In the PCP theorem showed, with others, how to encode a proof so that its correctness could be verified with high probability by sampling a constant number of bits. The result implies the hardness of approximation for many combinatorial problems and led to the invention of locally testable error-correcting codes, the field of algorithmic property testing, and classification of the intractability of large classes of optimization problems. Showed how to list-decode the Reed-Solomon code, which launched new research directions and became a proof technique used in the study of average case vs. worst case complexity. Awarded the Rolf Nevanlinna Prize (2002) for outstanding contributions to the mathematics of computer science and the G?del Prize (2000) in theoretical computer science.