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. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Lecture Notes in Computer Science. No.8096. Springer , Berlin, pp. 468-483. ISBN 978-3-642-40327-9.

[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:Book Section
Related URLs:
URLURL TypeDescription ReadCube access Paper
Vidick, Thomas0000-0002-6405-365X
Additional Information:© 2013 Springer-Verlag Berlin Heidelberg. 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. T.V. thanks Andy Drucker and Avi Wigderson for discussions. M.C. and H.Y. thank Scott Aaronson for his engaging class on Quantum Complexity Theory, for which some of the upper bounds were developed as a course project. H.Y. also thanks Joseph Bebel for helpful comments. We thank the anonymous RANDOM referees as well as Marco Tomamichel for comments that helped improve the presentation of our paper.
Funding AgencyGrant Number
Ministry of Education (Singapore)MOE2012-T3-1-009
NSF Graduate Research FellowshipDGE-1122374
Subject Keywords:Full Version; Seed Length; Ideal Strategy; Exponential Expansion; Ideal Device
Series Name:Lecture Notes in Computer Science
Issue or Number:8096
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 Nov 2021 23:46

Repository Staff Only: item control page