Fourier concentration from shrinkage

DOI10.1007/s00037-016-0134-yzbMath1371.68092OpenAlexW2393330754MaRDI QIDQ2012185

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

zbMATH Keywords

formula complexityrandom restrictionsshrinkage exponentaverage sensitivityde Morgan formulasFourier analysis of Boolean functionsFourier concentrationread-once de Morgan formulas

Mathematics Subject Classification ID

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)

Related Items (4)

Quantified Derandomization: How to Find Water in the Ocean ⋮ Correlation bounds and \#SAT algorithms for small linear-size circuits ⋮ Fourier concentration from shrinkage ⋮ Negation-limited formulas

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A satisfiability algorithm and average-case hardness for formulas over the full binary basis
• Turing machines that take advice
• Learning probabilistic read-once formulas on product distributions
• \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
• Hardness vs randomness
• On the shrinkage exponent for read-once formulae
• The average sensitivity of square-freeness
• An \(O(n^{\log \log n})\) learning algorithm for DNF under the uniform distribution
• Fourier concentration from shrinkage
• Mining circuit lower bound proofs for meta-algorithms
• Improving Exhaustive Search Implies Superpolynomial Lower Bounds
• An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas
• Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound
• Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer
• Constant depth circuits, Fourier transform, and learnability
• Nonuniform ACC Circuit Lower Bounds
• Short monotone formulae for the majority function
• Parity, circuits, and the polynomial-time hierarchy
• Circuit-size lower bounds and non-reducibility to sparse sets
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• Polylogarithmic independence fools AC ⁰ circuits
• A theory of the learnable
• A Pseudorandom Generator from any One-way Function
• How Do Read-Once Formulae Shrink?
• The Shrinkage Exponent of de Morgan Formulas is 2
• Shrinkage of de Morgan formulae under restriction
• Analysis of Boolean Functions
• Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function
• On the Correlation of Parity and Small-Depth Circuits
• Pseudorandomness from Shrinkage
• Probability Inequalities for Sums of Bounded Random Variables
• Quantum lower bounds by polynomials
• Average-case lower bounds for formula size
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Pseudo-random generators for all hardnesses

This page was built for publication: Fourier concentration from shrinkage