Improved Pseudorandom Generators for Depth 2 Circuits

DOI10.1007/978-3-642-15369-3_38zbMath1305.68128OpenAlexW1544713780MaRDI QIDQ3588430

Luca Trevisan, Anindya De, Omid Etesami, Madhur Tulsiani

Publication date: 10 September 2010

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-15369-3_38

zbMATH Keywords

pseudorandom generatorsDNFsmall bias spaces

Mathematics Subject Classification ID

Related Items (22)

A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3 ⋮ Entropy of Weight Distributions of Small-Bias Spaces and Pseudobinomiality ⋮ DNF sparsification and a faster deterministic counting algorithm ⋮ A Short Implicant of a CNF Formula with Many Satisfying Assignments ⋮ Pseudorandom generators for combinatorial checkerboards ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas ⋮ Almost k-Wise Independent Sets Establish Hitting Sets for Width-3 1-Branching Programs ⋮ The Fourier Entropy–Influence Conjecture for Certain Classes of Boolean Functions ⋮ Small-bias is not enough to hit read-once CNF ⋮ Not all FPRASs are equal: demystifying FPRASs for DNF-counting ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A short implicant of a CNF formula with many satisfying assignments ⋮ Solving and sampling with many solutions ⋮ Near-optimal pseudorandom generators for constant-depth read-once formulas ⋮ Improved bounds for quantified derandomization of constant-depth circuits and polynomials ⋮ Fourier bounds and pseudorandom generators for product tests ⋮ Solving and sampling with many solutions: Satisfiability and other hard problems ⋮ A Polynomial-Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3

This page was built for publication: Improved Pseudorandom Generators for Depth 2 Circuits