A Caltech Library Service

Robust Randomness Amplifiers: Upper and Lower Bounds

Coudron, Matthew and Vidick, Thomas and Yuen, Henry (2013) Robust Randomness Amplifiers: Upper and Lower Bounds. . (Submitted)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


A recent sequence of works, initially motivated by the study of the nonlocal properties of entanglement, demonstrate that a source of information-theoretically certified randomness can be constructed based only on two simple assumptions: the prior existence of a short random seed and the ability to ensure that two black-box devices do not communicate (i.e. are non-signaling). We call protocols achieving such certified amplification of a short random seed randomness amplifiers. We introduce a simple framework in which we initiate the systematic study of the possibilities and limitations of randomness amplifiers. Our main results include a new, improved analysis of a robust randomness amplifier with exponential expansion, as well as the first upper bounds on the maximum expansion achievable by a broad class of randomness amplifiers. In particular, we show that non-adaptive randomness amplifiers that are robust to noise cannot achieve more than doubly exponential expansion. Finally, we show that a wide class of protocols based on the use of the CHSH game can only lead to (singly) exponential expansion if adversarial devices are allowed the full power of non-signaling strategies. Our upper bound results apply to all known non-adaptive randomness amplifier constructions to date.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Vidick, Thomas0000-0002-6405-365X
Additional Information:T.V. was supported by the National Science Foundation under Grant No. 0844626 and by and by the Ministry of Education, Singapore under the Tier 3 grant MOE2012-T3-1-009. H.Y. was supported by an NSF Graduate Fellowship Grant No. 1122374 and National Science Foundation Grant No. 1218547. M.C. was supported by the National Science Foundation under Grant No. 0801525
Funding AgencyGrant Number
Ministry of Education (Singapore)MOE2012-T3-1-009
NSF Graduate Research FellowshipDGE-1122374
Record Number:CaltechAUTHORS:20160318-153752227
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:65492
Deposited By: Tony Diaz
Deposited On:18 Mar 2016 22:50
Last Modified:10 Jul 2017 22:44

Repository Staff Only: item control page