TOC researcher earns 2014 Infosys Prize for Mathematical Sciences

It was recently announced that Madhu Sudan, an MIT adjunct professor and member of CSAIL's Theory of Computation, has been selected to receive the 2014 Infosys Prize for Mathematical Sciences.

Presented by the Infosys Science Foundation in India, the award is given annually to honor outstanding achievements of contemporary researchers and scientists across six categories. Each award carries a prize of a gold medal, a citation and a purse of approximately $90,000.

The award was given to Sudan for his contributions to probabilistically checkable proofs and error-correcting codes.

Probabilistic proof checking is an important tool in the verification of algorithms making sure that programs work correctly and do what they are supposed to do, said jury chair Srinivasa S. R. Varadhan. "[Sudan's] work in coding has resulted in better error-correcting codes that significantly impacts electronic communication and encryption."

The central theme of Prof. Sudan's work has been on how to efficiently extract useful information from data that has errors. This theme has wide-ranging applications: from theoretical (e.g., how to verify a proof) to practical (e.g., how to recover correct data stored on a CD when it gets scratched).

His contributions led to the development of a new way of writing proofs, called Probabilistically Checkable Proofs (PCP), whose correctness can be verified with high probability by checking them at very few locations. This result, famously known as the PCP Theorem, has been hailed as one of the most fundamental contributions of theoretical computer science, and is closely tied to proving inapproximability of several NP-hard problems. His subsequent work has had a fundamental impact on our understanding of PCPs.

Prof. Sudan's work on list-decoding opened up the possibility of correcting far larger number of errors in data than was previously thought possible. This brought a new vigor to the field of error-correcting codes, and has led to many more advances in this field.

More information is available on the Infosys site and in the below interview.