Extractors for Circuit Sources

DOI10.1137/11085983XzbMath1301.68195MaRDI QIDQ5494933

Emanuele Viola

Publication date: 30 July 2014

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

samplinglower boundslocal entropyextractorsbounded-depth circuitsaffine sourcescomplexity of distributions

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (6)

Bi-Lipschitz bijection between the Boolean cube and the Hamming ball ⋮ An Efficient Reduction from Two-Source to Nonmalleable Extractors: Achieving Near-Logarithmic Min-Entropy ⋮ Unnamed Item ⋮ Sampling Lower Bounds: Boolean Average-Case and Permutations ⋮ How to extract useful randomness from unreliable sources ⋮ Explicit two-source extractors and resilient functions

This page was built for publication: Extractors for Circuit Sources