CaltechAUTHORS
  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) http://resolver.caltech.edu/CaltechAUTHORS:20160318-153752227

[img] PDF - Submitted Version
See Usage Policy.

271Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20160318-153752227

Abstract

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
http://arxiv.org/abs/1305.6626arXivDiscussion Paper
ORCID:
AuthorORCID
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
Funders:
Funding AgencyGrant Number
NSF0844626
Ministry of Education (Singapore)MOE2012-T3-1-009
NSF Graduate Research FellowshipDGE-1122374
NSF1218547
NSFDGE-0801525
Record Number:CaltechAUTHORS:20160318-153752227
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20160318-153752227
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:65492
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:18 Mar 2016 22:50
Last Modified:10 Jul 2017 22:44

Repository Staff Only: item control page