Improved Pseudorandom Generators for Depth 2 Circuits
From MaRDI portal
Publication:3588430
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
Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items
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
