N.R. Kamath Chair Colloquium on "Proofs and Computation"
IIT Bombay organised its Fourth N. R. Kamath Chair Colloquium on "Proofs and Computation" on 4th January , 2017.
Title : "Proofs and Computation"
Speaker : Prof. Madhu Sudan
NR Kamath Chair Professor at IIT Bombay,
Gordon McKay Professor of Computer Science,
Harvard John A. Paulson School of Engineering,
and Applied Sciences
While it is well-understood that Proofs form the foundations of Mathematics, it is less well-known that Proofs and Computers are intimately related. Indeed a common perception is that the only link between Proofs and Computing is that sometimes computers can assist in the search for proofs. In this talk Prof. Madhu Sudan will describe a more historically significant, and intrinsic, connection. Proofs by definition are "Computational Objects" - and to understand the difference between a theorem and its proof, one needs to understand computational complexity of tasks - namely the number of steps on a computer needed to solve a given task. In this talk, Prof. Madhu Sudan will talk about the historical role of proofs in computation, leading to the "prototype" of the modern computer in the 1930s, to the conception of the famous "Is P = NP?" question in the 1970s and some modern variation like interactive proofs, zero-knowledge proofs and probabilistically checkable proofs. The speaker will explain how at each stage the study of proofs has revolutionized the understanding of what computers can or can not do!
About the Speaker:
Prof. Madhu Sudan is a Gordon McKay Professor in the John A. Paulson School of Engineering and Applied Sciences at Harvard University. He obtained his Bachelors degree from IIT Delhi in 1987 and his Ph.D. from U.C. Berkeley in 1992. Between 1992 and 2015, he worked at IBM Research (Research Staff Member 1992-1997), at MIT (Associate Professor 1997-2000, Professor 2000-2011, Fujitsu Chair Professor 2003-2011, CSAIL Associate Director 2007-2009, Adjunct Professor,2011-2015), and at Microsoft Research (Principal Researcher, 2009-2015). He has been at Harvard since October 2015.
Prof. Madhu Sudan's research interests revolve around theoretical studies of communication and computation. Specifically his research focuses on concepts of reliability and mechanisms that are, or can be, used by computers to interact reliably with each other. His research draws on tools from computational complexity, which studies efficiency of computation, and many areas of mathematics including algebra and probability theory. He is best known for his works on probabilistic checking of proofs, and on the design of list-decoding algorithms for error-correcting codes.
In 2002, Madhu Sudan was awarded the Nevanlinna Prize, for outstanding contributions to the mathematics of computer science, at the International Congress of Mathematicians in Beijing. He is also the recipient of the 2014 Infosys Foundation Prize in Mathematical Sciences. Madhu Sudan is a fellow of the ACM, the IEEE, the AMS and the American Academy of Arts and Sciences. He was a Radcliffe Fellow from 2003-2004.