Bounded-depth circuits cannot sample good codes
From MaRDI portal
Publication:692999
DOI10.1007/S00037-012-0039-3zbMATH Open1282.68125OpenAlexW2152587816MaRDI QIDQ692999FDOQ692999
Authors: Shachar Lovett, Emanuele Viola 
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
Recommendations
- Tight Bounds on Computing Error-Correcting Codes by Bounded-Depth Circuits With Arbitrary Gates
- Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates
- Non-malleable codes for bounded depth, bounded fan-in circuits
- On the complexity of binary samples
- scientific article; zbMATH DE number 7250153
- Hardness-randomness tradeoffs for bounded depth arithmetic circuits
- Bounds for code length for circuits of functional elements
- Decoding by Sampling: A Randomized Lattice Algorithm for Bounded Distance Decoding
- scientific article; zbMATH DE number 1372652
- On the depth of randomly generated circuits
Cites Work
- Random generation of combinatorial structures from a uniform distribution
- A note on the edges of the n-cube
- Extractors for Circuit Sources
- Optimal Assignments of Numbers to Vertices
- Constant depth circuits, Fourier transform, and learnability
- The average sensitivity of bounded-depth circuits
- Pseudorandom bits for constant depth circuits
- The complexity of constructing pseudorandom generators from hard functions
- Polylogarithmic independence fools \(\mathrm{AC}^{0}\) circuits
- A Simple Proof of Bazzi’s Theorem
- Polylogarithmic independence can fool DNF formulas
- Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes
- The cell probe complexity of succinct data structures
- The complexity of distributions
- On the cell probe complexity of polynomial evaluation
- The Quantum Communication Complexity of Sampling
- On the implementation of huge random objects
- Bounded-depth circuits cannot sample good codes
Cited In (10)
- Complexity of quantum circuits via sensitivity, magic, and coherence
- Sampling Lower Bounds: Boolean Average-Case and Permutations
- Bounded-depth circuits cannot sample good codes
- On Lipschitz Bijections Between Boolean Functions
- On the minimum depth of circuits with linear number of wires encoding good codes
- On mappings on the hypercube with small average stretch
- Lipschitz bijections between boolean functions
- The complexity of distributions
- Title not available (Why is that?)
- Bi-Lipschitz bijection between the Boolean cube and the Hamming ball
This page was built for publication: Bounded-depth circuits cannot sample good codes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q692999)
