On the power of small-depth computation

DOI10.1561/0400000033MaRDI QIDQ3400006zbMATH OpenOpenAlexFDO

Authors Emanuele Viola

Publication date 18 January 2010

Published in Foundations and Trends® in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1561/0400000033

zbMATH Keywords

cryptography in bounded depth

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the power of small-depth threshold circuits
• Depth reduction for circuits of unbounded fan-in
• scientific article; zbMATH DE number 176874
• Exponential lower bounds for depth three Boolean circuits
• Optimal depth, very small size circuits for symmetric functions in \(AC^ 0\)

Cited in

(21)

• Local reduction
• The function-inversion problem: barriers and opportunities
• Block-symmetric polynomials correlate with parity better than symmetric
• Correlation lower bounds from correlation upper bounds
• Computation with Narrow CTCs
• On the Computational Complexity of Small Descriptions
• Arithmetic circuits: the chasm at depth four gets wider
• Towards hardness of approximation for polynomial time problems
• The minrank of random graphs
• Luby-Veličković-Wigderson revisited: improved correlation bounds and pseudorandom generators for depth-two circuits
• scientific article; zbMATH DE number 7528580 (Why is no real title available?)
• Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
• The strength of non-size increasing computation
• Improved pseudorandom generators from pseudorandom multi-switching lemmas
• Small PCPs with low query complexity
• scientific article; zbMATH DE number 7758331 (Why is no real title available?)
• Depth-3 circuits for inner product
• On the power of adaptivity for function inversion
• A technique for hardness amplification against AC^0
• Circuit depth reductions
• Fourier conjectures, correlation bounds, and majority

This page was built for publication: On the power of small-depth computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3400006)