On TC^0 lower bounds for the permanent

DOI10.1007/978-3-642-32241-9_36MaRDI QIDQ2914346zbMATH OpenOpenAlexFDO

Authors Jeff Kinne

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_36

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
• Upper and lower bounds for some depth-3 circuit classes
• A Uniform Circuit Lower Bound for the Permanent
• Lower bounds against weakly uniform circuits

Cited in

(7)

• Marginal hitting sets imply super-polynomial lower bounds for permanent
• Lower bounds against weakly uniform circuits
• 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
• Bootstrapping results for threshold circuits ``just beyond known lower bounds

This page was built for publication: On \(\mathrm{TC}^{0}\) lower bounds for the permanent

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