Fourier concentration from shrinkage
DOI10.1007/S00037-016-0134-YzbMATH Open1371.68092OpenAlexW2393330754MaRDI QIDQ2012185FDOQ2012185
Russell Impagliazzo, Valentine Kabanets
Publication date: 28 July 2017
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-016-0134-y
random restrictionsshrinkage exponentaverage sensitivityformula complexityde Morgan formulasFourier analysis of Boolean functionsFourier concentrationread-once de Morgan formulas
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Probability Inequalities for Sums of Bounded Random Variables
- Hardness vs randomness
- Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer
- A Pseudorandom Generator from any One-way Function
- Analysis of Boolean Functions
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- Constant depth circuits, Fourier transform, and learnability
- A theory of the learnable
- Parity, circuits, and the polynomial-time hierarchy
- Short monotone formulae for the majority function
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Mining circuit lower bound proofs for meta-algorithms
- A satisfiability algorithm and average-case hardness for formulas over the full binary basis
- Polylogarithmic independence fools AC 0 circuits
- The Shrinkage Exponent of de Morgan Formulas is 2
- Shrinkage of de Morgan formulae under restriction
- Pseudorandomness from Shrinkage
- Quantum lower bounds by polynomials
- Average-case lower bounds for formula size
- An \(O(n^{\log \log n})\) learning algorithm for DNF under the uniform distribution
- Fourier concentration from shrinkage
- An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas
- Circuit-size lower bounds and non-reducibility to sparse sets
- Turing machines that take advice
- Pseudo-random generators for all hardnesses
- The average sensitivity of square-freeness
- Improving exhaustive search implies superpolynomial lower bounds
- Nonuniform ACC Circuit Lower Bounds
- On the shrinkage exponent for read-once formulae
- How Do Read-Once Formulae Shrink?
- Learning probabilistic read-once formulas on product distributions
- Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound
- On the Correlation of Parity and Small-Depth Circuits
Cited In (6)
This page was built for publication: Fourier concentration from shrinkage
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2012185)
