Improved Pseudorandom Generators for Depth 2 Circuits
From MaRDI portal
Publication:3588430
DOI10.1007/978-3-642-15369-3_38zbMath1305.68128MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Related Items
Unnamed Item, Unnamed Item, Unnamed Item, A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas, Near-optimal pseudorandom generators for constant-depth read-once formulas, Fourier bounds and pseudorandom generators for product tests, Solving and sampling with many solutions: Satisfiability and other hard problems, Unnamed Item, A Polynomial-Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3, Paradigms for Unconditional Pseudorandom Generators, DNF sparsification and a faster deterministic counting algorithm, Pseudorandom generators for combinatorial checkerboards, Small-bias is not enough to hit read-once CNF, A short implicant of a CNF formula with many satisfying assignments, Not all FPRASs are equal: demystifying FPRASs for DNF-counting, Solving and sampling with many solutions, Improved bounds for quantified derandomization of constant-depth circuits and polynomials, A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3, A Short Implicant of a CNF Formula with Many Satisfying Assignments, 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, Entropy of Weight Distributions of Small-Bias Spaces and Pseudobinomiality
