Improved bounds for quantified derandomization of constant-depth circuits and polynomials

DOI10.1007/s00037-019-00179-2zbMath1425.68133OpenAlexW2572288605MaRDI QIDQ2311548

Roei Tell

Publication date: 10 July 2019

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7534/

zbMATH Keywords

derandomizationconstant-depth circuitsswitching lemmaquantified derandomizationhittingset generatorpolynomials that vanish rarely

Mathematics Subject Classification ID

Related Items (3)

Quantified Derandomization: How to Find Water in the Ocean ⋮ Unnamed Item ⋮ On hitting-set generators for polynomials that vanish rarely

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• DNF sparsification and a faster deterministic counting algorithm
• On the minimal Fourier degree of symmetric Boolean functions
• The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Equations over finite fields. An elementary approach
• Hardness vs randomness
• Certifying polynomials for AC^0(parity) circuits, with applications
• Pseudorandom Bits for Polynomials
• Pseudorandom generators for low degree polynomials
• Improved Pseudorandom Generators for Depth 2 Circuits
• Pseudorandom Bit Generators That Fool Modular Sums
• Analysis of Boolean Functions
• On derandomizing algorithms that err extremely rarely
• Introduction to Property Testing
• The Monotone Complexity of $k$-Clique on Random Graphs
• Extractors and pseudorandom generators
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding

This page was built for publication: Improved bounds for quantified derandomization of constant-depth circuits and polynomials