** 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