[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

 *REMINDER*

THEORY SEMINAR:


Tuesday, April 29, 2014
3:00 pm
Ryerson 251


Yaoyun Shi
University of Michigan
https://web.eecs.umich.edu/~shiyy/
 
Title: “True Randomness: Its Origin and Expansion”
 
Abstract:
How can we produce randomness of almost perfect quality, in large quantities, and under minimal assumptions? This question is fundamental not only to modern day information processing but also to physics. Yet a  satisfactory answer is still elusive to both the  practice and the theory of randomness extraction.
 
Here we propose a solution through a new paradigm of  extracting randomness from physical systems and basing security on the validity of physical theories, such as  quantum mechanics and special relativity. We construct  such "physical extractors" extracting from non-interacting quantum devices, whose inner-workings may be imperfect or even malicious. Composing our extractors gives a protocol that starts with a single and arbitrarily weak source of a fixed length and produces an arbitrarily long random output of  close to optimal quality and provable security against  all-powerful quantum adversaries. Several desirable  features of our protocols, including tolerance of  device imprecision, enable their implementations with the current quantum technology.
 
Our work also implies that unless the world is deterministic, we can experimentally create inherently random events and  be confident of their unpredictability. It thus provides  a practical and strongest method known for mitigating the  "freedom of choice" loophole for experimentally validating quantum mechanics.
 
Based on joint works with Kai-Min Chung and Xiaodi Wu
(arXiv:1402.4797), and Carl A. Miller (arXiv:1402.0489).
 
About the speaker:
Yaoyun Shi received his Bachelor's degree from Beijing University in 1997 and his PhD from Princeton University in 2001, both in Computer Science. He was a postdoc at the Institute of Quantum Information at Caltech and is currently an Associate Professor at the University of Michigan, Ann Arbor. His research focuses on the theory of quantum information processing.
 
 
Hosts: Prof. Razborov
(Refreshments will be served prior to the talk in Ryerson 255 @ 2:30)
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20140429/a41ea204/attachment.htm