On randomness extraction in AC^0

DOI10.4230/LIPICS.CCC.2015.601MaRDI QIDQ4601849zbMATH OpenWikidataFDO

Authors Oded Goldreich, Emanuele Viola, A. Wigderson

Publication date 24 January 2018

Full work available at URL https://doi.org/10.4230/LIPICS.CCC.2015.601

zbMATH Keywords

\({\mathcal{AC}}^0\)bit-fixing sourcesblock sourcesgeneral min-entropy sourcesmultiple-source extractionrandomness extractors

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Randomness extraction in \(\mathsf{AC}^0\) and with small locality
• Extractors for circuit sources
• Deterministic Extractors for Independent-Symbol Sources
• Simple extractors for all min-entropies and a new pseudorandom generator
• Deterministic Extractors for Bit‐Fixing Sources by Obtaining an Independent Seed

Cited in

(5)

• Randomness extraction in \(\mathsf{AC}^0\) and with small locality
• Quantified Derandomization: How to Find Water in the Ocean
• Extractors for circuit sources
• Randomness extractors in AC^0 and NC^1: optimal up to constant factors
• Low-degree polynomials are good extractors

This page was built for publication: On randomness extraction in \({\mathcal{AC}}^0\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4601849)