Fourier concentration from shrinkage
type: Item
instance of: scholarly article
title: Fourier concentration from shrinkage
zbMATH Open document ID: 1371.68092
author: Russell Impagliazzo
author: Valentine Kabanets
published in: Computational Complexity
publication date: 2017-07-28T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6754730
zbMATH Keywords: formula complexity
zbMATH Keywords: random restrictions
zbMATH Keywords: de Morgan formulas
zbMATH Keywords: read-once de Morgan formulas
zbMATH Keywords: shrinkage exponent
zbMATH Keywords: Fourier analysis of Boolean functions
zbMATH Keywords: Fourier concentration
zbMATH Keywords: average sensitivity
MaRDI profile type: Publication
full work available at URL: s00037-016-0134-y
OpenAlex ID: W2393330754
cites work: Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer
cites work: Q3772136
cites work: \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
cites work: Quantum lower bounds by polynomials
cites work: Short monotone formulae for the majority function
cites work: The average sensitivity of square-freeness
cites work: How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
cites work: Q3002797
cites work: Polylogarithmic independence fools AC 0 circuits
cites work: Mining circuit lower bound proofs for meta-algorithms
cites work: An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas
cites work: A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
cites work: How Do Read-Once Formulae Shrink?
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: Turing machines that take advice
cites work: Circuit-size lower bounds and non-reducibility to sparse sets
cites work: Derandomizing polynomial identity tests means proving circuit lower bounds
cites work: The Shrinkage Exponent of de Morgan Formulas is 2
cites work: On the Correlation of Parity and Small-Depth Circuits
cites work: A Pseudorandom Generator from any One-way Function
cites work: On the shrinkage exponent for read-once formulae
cites work: Probability Inequalities for Sums of Bounded Random Variables
cites work: Q5743451
cites work: Pseudorandomness from Shrinkage
cites work: Q4526985
cites work: Q5629239
cites work: Average-case lower bounds for formula size
cites work: Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound
cites work: Constant depth circuits, Fourier transform, and learnability
cites work: An \(O(n^{\log \log n})\) learning algorithm for DNF under the uniform distribution
cites work: Hardness vs randomness
cites work: Analysis of Boolean Functions
cites work: Shrinkage of de Morgan formulae under restriction
cites work: Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function
cites work: Q5365063
cites work: Q3549690
cites work: Learning probabilistic read-once formulas on product distributions
cites work: A satisfiability algorithm and average-case hardness for formulas over the full binary basis
cites work: Q3281059
cites work: Pseudo-random generators for all hardnesses
cites work: A theory of the learnable
cites work: Improving exhaustive search implies superpolynomial lower bounds
cites work: Nonuniform ACC Circuit Lower Bounds
DOI: 10.1007/S00037-016-0134-Y
description: scientific article; zbMATH DE number 6754730