Lower bounds against weakly uniform circuits

DOI10.1007/978-3-642-32241-9_35MaRDI QIDQ2914345zbMATH OpenOpenAlexFDO

Authors Ruiwen Chen, Valentine Kabanets

Publication date 25 September 2012

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-32241-9_35

zbMATH Keywords

advice complexity classesalternating Turing machinescounting hierarchypermanentsuccinct circuitsthreshold circuitsuniform circuit lower boundsweakly uniform circuits

Mathematics Subject Classification ID

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

Recommendations

• Lower bounds against weakly-uniform threshold circuits
• scientific article; zbMATH DE number 1351078
• Amplifying lower bounds by means of self-reducibility
• A Uniform Circuit Lower Bound for the Permanent
• On \(\mathrm{TC}^{0}\) lower bounds for the permanent

Cited in

(13)

• Feasibly constructive proofs of succinct weak circuit lower bounds
• The lower reaches of circuit uniformity
• On \(\mathrm{TC}^{0}\) lower bounds for the permanent
• Lower Bounds for Coin-Weighing Problems
• P-uniform circuit complexity
• Amplifying circuit lower bounds against polynomial time, with applications
• scientific article; zbMATH DE number 1351078 (Why is no real title available?)
• A Uniform Circuit Lower Bound for the Permanent
• Lower bounds against weakly-uniform threshold circuits
• On uniformity and circuit lower bounds
• Easiness amplification and uniform circuit lower bounds
• Mathematical Foundations of Computer Science 2004
• Proving Circuit Lower Bounds in High Uniform Classes

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

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