Title : "Proofs and Computation"
Speaker : Prof. Madhu Sudan, N.R. Kamath Chair Professor at IIT Bombay, Gordon McKay Professor of computer Science, Harvard John A. Paulson School of Engineering and Applied Sciences
Abstract: 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!