On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy

DOI10.1137/S0097539703422716MaRDI QIDQ4651502zbMATH OpenFDO

Authors Jin-Yi Cai, Osamu Watanabe

Publication date 21 February 2005

Published in SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

computational complexitycircuit complexitystringent relativizationNisan-Wigderson generatorSwitching Lemma

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

• On proving circuit lower bounds against the polynomial-time hierarchy: positive and negative results
• scientific article; zbMATH DE number 806749
• Proof complexity lower bounds from algebraic circuit complexity
• scientific article; zbMATH DE number 7471587
• Proving Circuit Lower Bounds in High Uniform Classes
• Polynomial time ultrapowers and the consistency of circuit lower bounds
• On Circuit-Size Complexity and the Low Hierarchy in NP
• Lower bounds: from circuits to QBF proof systems
• On the limit of some algorithmic approach to circuit lower bounds
• Feasibly constructive proofs of succinct weak circuit lower bounds

Cited in

(13)

• On solving hard problems by polynomial-size circuits
• On proving circuit lower bounds against the polynomial-time hierarchy: positive and negative results
• Feasibly constructive proofs of succinct weak circuit lower bounds
• Circuit lower bounds à la Kolmogorov
• scientific article; zbMATH DE number 1222575 (Why is no real title available?)
• On Circuit-Size Complexity and the Low Hierarchy in NP
• Proving Circuit Lower Bounds in High Uniform Classes
• Lower bounds: from circuits to QBF proof systems
• scientific article; zbMATH DE number 6866317 (Why is no real title available?)
• scientific article; zbMATH DE number 7009617 (Why is no real title available?)
• scientific article; zbMATH DE number 7471587 (Why is no real title available?)
• Parity, circuits, and the polynomial-time hierarchy
• On the limit of some algorithmic approach to circuit lower bounds

This page was built for publication: On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy

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