Fourier concentration from shrinkage

DOI10.1007/S00037-016-0134-YMaRDI QIDQ2012185zbMATH OpenOpenAlexFDO

Authors 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

random restrictionsshrinkage exponentaverage sensitivityformula complexityde 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)

Recommendations

• Shrinkage of de Morgan formulae under restriction
• Which bases admit non-trivial shrinkage of formulae?
• On the shrinkage exponent for read-once formulae
• The Shrinkage Exponent of de Morgan Formulas is 2
• Which formulae shrink under random restrictions?

Cites work

• scientific article; zbMATH DE number 5899272 (Why is no real title available?)
• scientific article; zbMATH DE number 3162894 (Why is no real title available?)
• scientific article; zbMATH DE number 5485521 (Why is no real title available?)
• scientific article; zbMATH DE number 4031582 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• scientific article; zbMATH DE number 3354614 (Why is no real title available?)
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• A Pseudorandom Generator from any One-way Function
• A satisfiability algorithm and average-case hardness for formulas over the full binary basis
• A satisfiability algorithm for \(\mathrm{AC}^0\)
• A theory of the learnable
• An \(O(n^{\log \log n})\) learning algorithm for DNF under the uniform distribution
• An improved deterministic \#SAT algorithm for small De Morgan formulas
• Analysis of Boolean Functions
• Any AND-OR formula of size \(N\) can be evaluated in time \(N^{1/2+o(1)}\) on a quantum computer
• Average-case lower bounds for formula size
• Circuit-size lower bounds and non-reducibility to sparse sets
• Constant depth circuits, Fourier transform, and learnability
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Fourier concentration from shrinkage
• Hardness vs randomness
• How Do Read-Once Formulae Shrink?
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• Improved average-case lower bounds for De Morgan formula size: matching worst-case lower bound
• Improving exhaustive search implies superpolynomial lower bounds
• Learning probabilistic read-once formulas on product distributions
• Mining circuit lower bound proofs for meta-algorithms
• Nonuniform ACC circuit lower bounds
• On the Correlation of Parity and Small-Depth Circuits
• On the shrinkage exponent for read-once formulae
• Parity, circuits, and the polynomial-time hierarchy
• Polylogarithmic independence fools \(\mathrm{AC}^{0}\) circuits
• Probability Inequalities for Sums of Bounded Random Variables
• Pseudo-random generators for all hardnesses
• Pseudorandomness from shrinkage
• Quantum lower bounds by polynomials
• Reflections for quantum query algorithms
• Short monotone formulae for the majority function
• Shrinkage of de Morgan formulae under restriction
• Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function
• The Shrinkage Exponent of de Morgan Formulas is 2
• The average sensitivity of square-freeness
• Turing machines that take advice
• BPP has subexponential time simulations unless EXPTIME has publishable proofs

Cited in

(6)

• Fourier concentration from shrinkage
• Which bases admit non-trivial shrinkage of formulae?
• Which formulae shrink under random restrictions?
• Negation-limited formulas
• Quantified Derandomization: How to Find Water in the Ocean
• Correlation bounds and \#SAT algorithms for small linear-size circuits

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)