Date: Wednesday, January 28, 2002
Time: 4:00 PM (talk)
3:00 PM (reception in the Parks Shop Lounge)
Place: Parks Shop, Studio 1, NCSU Historical Campus
(click for courtesy parking request)
Speaker: Nicholas Pippenger , Computer Science, University of British Columbia
Computation in the Presence of Noise: Classical and Quantum
Abstract: In a famous series of lectures given in 1952, John von Neumann showed that reliable computers could be built from unreliable components. His ideas have not had much influence on practical computing, because computer components have always been sufficiently reliable that the use of techniques such as those von Neumann proposed have been justified only in extreme cases. Nevertheless, von Neumann's ideas have led to a number of developments in theoretical computer science; in particular, they provided one of the earliest opportunities for the use of expanding graphs in derandomization of computations. By now, however, the possibilites and limitations in this area are fairly well understood.
Quantum computers were proposed in the 1980s, but attracted widespread attention in 1994, when Peter Shor showed that they could solve in polynomial time some problems (such as the factorization of large integers) for which no polynomial-time classical algorithms are known. Here the situation is reversed: we cannot built quantum computing components with reliability anywhere near that needed to carry out quantum computations on a scale at which they are competitive with classical computations, and so a quantum analogue of von Neumann's theory will surely be essential if quantum computation ever becomes practical. But in the quantum setting, many basic issues about what is possible remain to be resolved.
Short Bio: Nicholas Pippenger holds a Canada Research Chair in Computer Science at the University of British Columbia. He received the Ph. D. in Electrical Engineering from MIT in 1974. He worked for IBM at the Thomas J. Watson Research Center from 1973 to 1980, and at the San Jose Research Laboratory (later the Almaden Research Center) from 1980 to 1989. He was named an IBM Fellow in 1987. Since 1988 he has been a Professor in the Computer Science Department at the University of British Columbia. His research interests centre in theoretical computer science, but also extend into communication theory and mathematics. Nicholas Pippenger is a Fellow of the Royal Society of Canada (Academy of Science), a Fellow of the Institute of Electrical and Electronics Engineers, and a Fellow of the Association for Computing Machinery. He is a member of the American Mathematical Association, the Mathematical Association of America and the Society for Industrial and Applied Mathematics. He is the author of "Theories of Computability", published by Cambridge University Press in 1997.
Host: F. Brglez , Computer Science, NCSU