Lower bounds against weakly-uniform threshold circuits

DOI10.1007/S00453-013-9823-YzbMATH Open1314.68142OpenAlexW2078952510MaRDI QIDQ486977FDOQ486977

Authors Ruiwen Chen, Valentine Kabanets, Jeff Kinne

Publication date 19 January 2015

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-013-9823-y

zbMATH Keywords

permanentthreshold circuitscounting hierarchyadvice complexity classesalternating Turing machinessuccinct circuitsuniform circuit lower boundsweakly-uniform circuits

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Lower bounds against weakly uniform circuits
• On \(\mathrm{TC}^{0}\) lower bounds for the permanent
• scientific article; zbMATH DE number 1351078
• scientific article; zbMATH DE number 1256716
• A Uniform Circuit Lower Bound for the Permanent

Cites work

• scientific article; zbMATH DE number 3133387 (Why is no real title available?)
• scientific article; zbMATH DE number 3759547 (Why is no real title available?)
• scientific article; zbMATH DE number 1335875 (Why is no real title available?)
• scientific article; zbMATH DE number 1351078 (Why is no real title available?)
• scientific article; zbMATH DE number 1929951 (Why is no real title available?)
• scientific article; zbMATH DE number 1405686 (Why is no real title available?)
• #P-COMPLETENESS VIA MANY-ONE REDUCTIONS
• A Turing machine time hierarchy
• A Uniform Circuit Lower Bound for the Permanent
• Alternation
• Circuit-size lower bounds and non-reducibility to sparse sets
• Complexity classes defined by counting quantifiers
• Computational Complexity
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Explicit lower bound of 4.5n - o(n) for boolena circuits
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Languages to diagonalize against advice classes
• Log Space Recognition and Translation of Parenthesis Languages
• Lower bounds against weakly uniform circuits
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Natural proofs
• Nonuniform lower bounds for exponential time classes
• On ACC
• On \(\mathrm{TC}^{0}\) lower bounds for the permanent
• On uniform circuit complexity
• On uniformity within \(NC^ 1\)
• PP is as Hard as the Polynomial-Time Hierarchy
• Parallel computation with threshold functions
• Parity, circuits, and the polynomial-time hierarchy
• Permanent does not have succinct polynomial size arithmetic circuits of constant depth
• The complexity of combinatorial problems with succinct input representation
• The complexity of computing the permanent
• The power of the middle bit of a \(\#\)P function
• Turing machines that take advice

Cited in

(3)

• A Uniform Circuit Lower Bound for the Permanent
• Lower bounds against weakly uniform circuits
• On \(\mathrm{TC}^{0}\) lower bounds for the permanent

This page was built for publication: Lower bounds against weakly-uniform threshold circuits

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