Date and Time

Tuesday, March 27, 2012 - 4:30pm to 5:30pm

Location

Computer Science Small Auditorium (Room 105)

Type

CS Department Colloquium Series

Speaker

Host

Sanjeev Arora

A source of independent and uniform random bits is a basic resource in many computational
tasks, such as cryptography, game theoretic protocols, algorithms and physical simulations.
In the classical world it is impossible to construct a random number generator whose output
can be certified to be a uniformly random n-bit string, since there seems to be no basis on
which to reject any particular output in favor of any other. Quantum mechanics allows for a
remarkable random number generator: its output is certifiably random in the sense that if the
output passes a simple statistical test, and a no-signaling condition is met between the two
boxes in the randomness generating device (based, say, on the speed of light limit imposed
by special relativity), even a quantum skeptic (viz Einstein's famous quote ``God does not
play dice with the Universe''), would be convinced that the output is truly random, independent
of the validity of quantum mechanics.
Based on joint work with Thomas Vidick.