Bounded-depth circuits cannot sample good codes
From MaRDI portal
(Redirected from Publication:692999)
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
- A note on the edges of the n-cube
- A simple proof of Bazzi's theorem
- Bounded-depth circuits cannot sample good codes
- Constant depth circuits, Fourier transform, and learnability
- Extractors for Circuit Sources
- On the cell probe complexity of polynomial evaluation
- On the implementation of huge random objects
- Optimal Assignments of Numbers to Vertices
- Polylogarithmic independence can fool DNF formulas
- Polylogarithmic independence fools \(\mathrm{AC}^{0}\) circuits
- Pseudorandom bits for constant depth circuits
- Random generation of combinatorial structures from a uniform distribution
- The Quantum Communication Complexity of Sampling
- The average sensitivity of bounded-depth circuits
- The cell probe complexity of succinct data structures
- The complexity of constructing pseudorandom generators from hard functions
- The complexity of distributions
- Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes
Cited in
(11)- Complexity of quantum circuits via sensitivity, magic, and coherence
- Bounded-depth circuits cannot sample good codes
- Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates
- 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
- Sampling lower bounds: Boolean average-case and permutations
- scientific article; zbMATH DE number 7650118 (Why is no real title available?)
- Bi-Lipschitz bijection between the Boolean cube and the Hamming ball
- On Lipschitz bijections between Boolean functions
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)
