Bounded-depth circuits cannot sample good codes

DOI10.1007/s00037-012-0039-3zbMath1282.68125MaRDI QIDQ692999

Emanuele Viola, Shachar Lovett

Publication date: 7 December 2012

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

Full work available at URL: https://doi.org/10.1007/s00037-012-0039-3

zbMATH Keywords

sampling; isoperimetric inequalities; noise sensitivity; small depth circuits

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

On Lipschitz Bijections Between Boolean Functions, Sampling Lower Bounds: Boolean Average-Case and Permutations, Unnamed Item, On mappings on the hypercube with small average stretch, Lipschitz bijections between boolean functions, Bounded-depth circuits cannot sample good codes, Bi-Lipschitz bijection between the Boolean cube and the Hamming ball

Cites Work

• The average sensitivity of bounded-depth circuits
• On the cell probe complexity of polynomial evaluation
• Bounded-depth circuits cannot sample good codes
• Pseudorandom bits for constant depth circuits
• Random generation of combinatorial structures from a uniform distribution
• A note on the edges of the n-cube
• The complexity of constructing pseudorandom generators from hard functions
• The cell probe complexity of succinct data structures
• The Complexity of Distributions
• A Simple Proof of Bazzi’s Theorem
• Constant depth circuits, Fourier transform, and learnability
• Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes
• Polylogarithmic independence fools AC ⁰ circuits
• Polylogarithmic Independence Can Fool DNF Formulas
• The Quantum Communication Complexity of Sampling
• On the Implementation of Huge Random Objects
• Extractors for Circuit Sources
• Optimal Assignments of Numbers to Vertices