Bounded-depth circuits cannot sample good codes

DOI10.1007/s00037-012-0039-3zbMath1282.68125OpenAlexW2152587816MaRDI 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

samplingisoperimetric inequalitiesnoise sensitivitysmall depth circuits

Mathematics Subject Classification ID

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

Related Items (7)

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

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

This page was built for publication: Bounded-depth circuits cannot sample good codes