This talk will focus on an exciting new area at the boundaries of Quantum Physics and Computer Science. Recent results have shown that computers based on Quantum mechanical interactions can solve certain computational problems exponentially faster than classical computers. A striking example of this is an algorithm for factoring integers efficiently on a quantum computer. The intractability of this problem on classical computers is the basis of the famous RSA scheme for public key cryptography. In this talk, I will discuss the fundamental principles underlying quantum computers and their novel algorithmic features. I will also briefly discuss the challenges that must be overcome to realize quantum computers, and the relevance of this area to the foundations of quantum physics.

Umesh Vazirani is an Associate Professor of Computer Science at the University of California, Berkeley. He received an NSF Presidential Young Investigator Award in 1987 and the Friedman Mathematics Prize in 1985. He has recently completed a book, ``An Introduction to Computational Learning Theory'' (with Michael Kearns), and currently at the forefront of research in the area of quantum computing.

This Forum is OPEN to the public.
Host: Marti Hearst, (415) 812-4742, hearst@parc.xerox.com