Improved pseudorandom generators for depth 2 circuits

DOI10.1007/978-3-642-15369-3_38MaRDI QIDQ3588430zbMATH OpenOpenAlexFDO

Authors Anindya De, Omid Etesami, Luca Trevisan, 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

DNFpseudorandom generatorssmall bias spaces

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Recommendations

• Polylogarithmic independence can fool DNF formulas
• Pseudorandomness for read-k DNF formulas
• More on bounded independence plus noise: pseudorandom generators for read-once polynomials
• Pseudorandomness from shrinkage
• Luby-Veličković-Wigderson revisited: improved correlation bounds and pseudorandom generators for depth-two circuits

Cited in

(36)

• Improved pseudorandom generators for combinatorial rectangles
• 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
• Pseudorandom generators for combinatorial shapes
• 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
• DNF sparsification and a faster deterministic counting algorithm
• Polylogarithmic independence can fool DNF formulas
• Pseudorandom generators for combinatorial checkerboards
• Bounded independence plus noise fools products
• Randomness buys depth for approximate counting
• A quadratic size-hierarchy theorem for small-depth multilinear formulas
• Deterministically counting satisfying assignments for constant-depth circuits with parity gates, with implications for lower bounds
• Luby-Veličković-Wigderson revisited: improved correlation bounds and pseudorandom generators for depth-two circuits
• scientific article; zbMATH DE number 7528580 (Why is no real title available?)
• Fourier bounds and pseudorandom generators for product tests
• Near-optimal pseudorandom generators for constant-depth read-once formulas
• scientific article; zbMATH DE number 7561734 (Why is no real title available?)
• Bounded independence plus noise fools products
• Solving and sampling with many solutions: satisfiability and other hard problems
• More on bounded independence plus noise: pseudorandom generators for read-once polynomials
• Small-bias is not enough to hit read-once CNF
• Pseudorandomness for read-k DNF formulas
• Pseudorandomness from shrinkage
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• A polynomial-time construction of a hitting set for read-once branching programs of width 3
• Improved pseudorandom generators from pseudorandom multi-switching lemmas
• Paradigms for Unconditional Pseudorandom Generators
• Deterministic document exchange protocols and almost optimal binary codes for edit errors
• Pseudorandom generators for unbounded-width permutation branching programs
• A short implicant of a CNF formula with many satisfying assignments
• Implications of better PRGs for permutation branching programs

This page was built for publication: Improved pseudorandom generators for depth 2 circuits

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