Extracting Randomness from Samplable Distributions, Revisited

Marshall Ball, Eli Goldin, Dana Dachman-Soled, Saachi Mutreja

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Randomness extractors provide a generic way of converting sources of randomness that are merely unpredictable into almost uniformly random bits. While in general, deterministic randomness extraction is impossible, it is possible if the source has some structural constraints.While much of the literature on deterministic extraction has focused on sources with strong independence properties, a natural class where deterministic extraction is possible is sources that can sampled by a polynomial size circuit, Levin [SIAM J Comp'86]. Trevisan and Vadhan [FOCS'00] explicitly constructed deterministic randomness extractors for this class of sources, assuming very strong circuit lower bounds.We suggest that there is perhaps an even more reasonable model of natural sources of randomness than Levin's: sources sampled by polynomial size quantum circuits. Under a suitable circuit lower bound, we show that Trevisan and Vadhan's extractor indeed works for this class.Along the way, we substantially improve their analysis in the classical case, showing that a circuit lower bound against NP-circuits suffice in the classical case (as opposed to a lower bounds on Σ_5-circuits, as shown by Trevisan and Vadhan). Moreover, we show that under this assumption, it is possible to handle sources sampled by postselecting circuits (a variant of nondeterministic circuits). We show that this model is sufficient to capture randomness extraction in the presence of efficiently computable leakage.

Original languageEnglish (US)
Title of host publicationProceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023
PublisherIEEE Computer Society
Number of pages10
ISBN (Electronic)9798350318944
StatePublished - 2023
Event64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023 - Santa Cruz, United States
Duration: Nov 6 2023Nov 9 2023

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428


Conference64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023
Country/TerritoryUnited States
CitySanta Cruz


  • average-case complexity
  • quantum computing
  • randomness in computing

ASJC Scopus subject areas

  • General Computer Science


Dive into the research topics of 'Extracting Randomness from Samplable Distributions, Revisited'. Together they form a unique fingerprint.

Cite this