<html><head><style type='text/css'>p { margin: 0; }</style></head><body><div style='font-family: arial,helvetica,sans-serif; font-size: 12pt; color: #000000'><b>Certifiable Quantum Dice</b>

<br>

<b><a href="http://www.cs.berkeley.edu/%7Evazirani/">Umesh Vazirani</a></b>, <a href="http://www.berkeley.edu/">University of California, Berkeley</a>

<br>Tuesday, March 27 4:30pm<br>Computer Science Small Auditorium (Room 105)<br>

<br>

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.

<div><span name="x"></span><br></div><br></div></body></html>