Randomness extraction in AC^0 and with small locality

DOI10.4230/LIPICS.APPROX-RANDOM.2018.37MaRDI QIDQ5009532zbMATH OpenFDO

Authors Kuan Cheng, Xin Li

Publication date 4 August 2021

Full work available at URL https://arxiv.org/abs/1602.01530

zbMATH Keywords

AC0localitypseudorandom generatorrandomness extraction

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• On randomness extraction in \({\mathcal{AC}}^0\)
• Extractors for circuit sources
• Simple extractors for all min-entropies and a new pseudorandom generator
• Extractors and pseudorandom generators
• Randomness extractors -- applications and constructions

Cites work

• BPP has subexponential time simulations unless EXPTIME has publishable proofs
• Advances in Cryptology - CRYPTO 2003
• Analysis of Boolean Functions
• Candidate one-way functions based on expander graphs
• Constant depth circuits, Fourier transform, and learnability
• Cryptography in NC^0
• Design extractors, non-malleable condensers and privacy amplification
• Deterministic Extractors for Bit‐Fixing Sources and Exposure‐Resilient Cryptography
• Deterministic Extractors for Bit‐Fixing Sources by Obtaining an Independent Seed
• Efficient cryptographic schemes provably as secure as subset sum
• Explicit Resilient Functions Matching Ajtai-Linial
• Explicit two-source extractors and resilient functions
• Exposure-resilient functions and all-or-nothing transforms
• Extractors and pseudorandom generators
• Extractors Using Hardness Amplification
• Hardness vs randomness
• scientific article; zbMATH DE number 1306886 (Why is no real title available?)
• scientific article; zbMATH DE number 1097580 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• On pseudorandom generators with linear stretch in \(\mathrm{NC}^{0}\)
• On randomness extraction in \({\mathcal{AC}}^0\)
• On ε‐biased generators in NC⁰
• Pseudorandom generators for space-bounded computation
• Pseudorandom generators with long stretch and low locality from random local one-way functions
• Pseudorandomness for network algorithms
• Randomness is linear in space
• Sparse extractor families for all the entropy
• The complexity of constructing pseudorandom generators from hard functions
• The influence of large coalitions
• Tight security proofs for the bounded-storage model
• Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes
• Universal classes of hash functions

Cited in

(6)

• Randomness-Efficient Sampling Within NC 1
• On randomness extraction in \({\mathcal{AC}}^0\)
• Explicit directional affine extractors and improved hardness for linear branching programs
• Randomness extractors in AC^0 and NC^1: optimal up to constant factors
• Low-degree polynomials are good extractors
• Randomness-efficient sampling within NC\(^{1}\)

This page was built for publication: Randomness extraction in \(\mathsf{AC}^0\) and with small locality

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