Bounded-depth circuits cannot sample good codes

DOI10.1007/S00037-012-0039-3MaRDI QIDQ692999zbMATHOpenAlexFDO

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

zbMATH Keywords

samplingisoperimetric inequalitiesnoise sensitivitysmall depth circuits

Mathematics Subject Classification ID

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

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)

• On the minimum depth of circuits with linear number of wires encoding good codes
• On mappings on the hypercube with small average stretch
• Complexity of quantum circuits via sensitivity, magic, and coherence
• Lipschitz bijections between boolean functions
• Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates
• scientific article; zbMATH DE number 7650118 (Why is no real title available?)
• Sampling lower bounds: Boolean average-case and permutations
• Bi-Lipschitz bijection between the Boolean cube and the Hamming ball
• Bounded-depth circuits cannot sample good codes
• On Lipschitz bijections between Boolean functions
• The complexity of distributions

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)