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

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

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)

Cites Work

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

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)