Near-optimal pseudorandom generators for constant-depth read-once formulas

DOI10.4230/LIPICS.CCC.2019.16OpenAlexW2794820917MaRDI QIDQ5091767

Dean Doron, Pooya Hatami, William M. Hoza

Publication date: 27 July 2022

Full work available at URL: https://dblp.uni-trier.de/db/conf/coco/coco2019.html#DoronHH19

zbMATH Keywords

explicit constructionspseudorandom generatorsconstant-depth formulas

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (4)

Unnamed Item ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Unnamed Item ⋮ A Polynomial-Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• DNF sparsification and a faster deterministic counting algorithm
• Pseudorandom bits for constant depth circuits
• Approximate inclusion-exclusion
• Pseudorandom generators for space-bounded computation
• Improved algorithms via approximations of probability distributions
• Pseudorandomness for Regular Branching Programs via Fourier Analysis
• A Simple Proof of Bazzi’s Theorem
• Almost k-Wise Independent Sets Establish Hitting Sets for Width-3 1-Branching Programs
• Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Pseudorandom Generators for Regular Branching Programs
• Parity, circuits, and the polynomial-time hierarchy
• Improved Pseudorandom Generators for Depth 2 Circuits
• Polylogarithmic Independence Can Fool DNF Formulas
• Simple Constructions of Almost k-wise Independent Random Variables
• On polynomial approximations to AC
• Bounded Independence Plus Noise Fools Products
• Pseudorandom generators for width-3 branching programs
• Improved pseudorandomness for unordered branching programs through local monotonicity
• Pseudorandomness for read-k DNF formulas
• Pseudorandomness from Shrinkage
• On derandomizing algorithms that err extremely rarely
• Explicit two-source extractors and resilient functions
• Pseudorandom generators for group products
• Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
• Pseudorandomness for Read-Once Formulas
• Automata, Languages and Programming

This page was built for publication: Near-optimal pseudorandom generators for constant-depth read-once formulas