(Computational) Complexity in Everyday Life
Prof. Madhu Sudan - Massachusetts Institute of Technology (MIT)
Martedì, 24 Marzo, 2009
 |
(Computational) Complexity in Everyday Life
Prof. Madhu Sudan - Massachusetts Institute of Technology (MIT) |
|
| Madhu Sudan received his Bachelor's degree from the Indian Institute of Technology at New Delhi in 1987 and his Ph.D. from the University of California at Berkeley in 1992. Currently he is the Fujitsu Professor of Electrical Engineering and Computer Science at MIT. Madhu Sudan's research interests include computational complexity theory, algorithms and coding 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. Madhu Sudan's other awards include the ACM Doctoral Dissertation Award (1992), the IEEE Information Theory Society Paper Award (2000) and the Godel Prize (2001), Distinguished Alumnus Award of the University of California at Berkeley (2003), and Distinguished Alumnus Award of the Indian Institute of Technology at Delhi (2004). Madhu Sudan is a Guggenheim Fellow (inducted 2005) and an ACM Fellow (inducted 2008). | Abstract The remarkable success of computers has led to two kinds of misconceptions about the "science behind computers": (1) The science represents the technology needed to build computers, and (2) The technology and science have accomplished almost everything we could wish for. In this talk we will try to allay these misconceptions by recalling the history of computer science, dating back to the Hilbert program and the works of Godel and Turing. Mathematical models of computers were developed well before we had any hope of building computers! We will then talk about modern elements of computing, including the famed "P vs. NP" question, and their philosophical implications (why computing matters to biologists, economists, lawyers and politicians, and not just mathematicians and engineers). I will conclude by explaining why computing is still in its infancy and talk about the emerging need for "Macro-Computer-Science": the science of large networks of disparate, selfish computers evolving together. |
Allegato: