Bounded-depth circuits cannot sample good codes
From MaRDI portal
Publication:692999
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
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 0 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