About the series
CISE Distinguished Lecture
Monday, March 23, 2009, Room 110, 11:00am - 12:00 p.m.
"Limits on Efficient Computation in the Physical World"
Scott Aaronson, Ph.D.
Massachusetts Institute of Technology
§§§
Abstract:
Can NP-complete and other "intractable" computational problems be feasibly solved by any physical means? I'll argue that this question is not just a practical matter for cryptography and software design ,but a contender for one of the great mysteries of 21st century science: a clear, easy-to-state question that nevertheless unifies some of the central intellectual concerns of math, physics, computer science, and even cognitive science and biology. I'll also describe how results from my own area, quantum computing, have reshaped our understanding of the question within the last fifteen years.
§§§
Bio:
Scott Aaronson is an Assistant Professor of Electrical Engineering and Computer Science, and a member of the Theory of Computation and Complexity Theory groups. He holds a PhD in computer science from University of California, Berkeley, a bachelor's degree from Cornell University, and a GED from New York State. Before coming to MIT, Aaronson worked as a postdoctoral researcher at the Institute for Advanced Study in Princeton, NJ from 2004-2005, and at the Institute for Quantum Computing at the University of Waterloo in Ontario, Canada from 2005-2007. His research interests center around fundamental limits on what can efficiently be computed in the physical world. This has entailed studying quantum computing, the most powerful model of computation we have based on known physical theory. His work on this subject has included limitations of quantum algorithms in the black-box model; algorithms for quantum spatial search and for simulating restricted classes of quantum circuits; the learnability of quantum states; quantum versus classical proofs and advice; and the power of postselected quantum computing and quantum computing with closed timelike curves. He also maintains an active interest in many topics in classical theoretical computer science including circuit lower bounds, computational learning theory, communication complexity, and Bayesian agreement and inference.
*For individual meeting time, please contact Iesha McGhee at x8241.
