On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy

DOI10.1137/S0097539703422716zbMATH Open1105.68041MaRDI QIDQ4651502FDOQ4651502

Authors: Jin-Yi Cai, Osamu Watanabe 

Publication date: 21 February 2005

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

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

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)

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
• Title not available (Why is that?)
• On Circuit-Size Complexity and the Low Hierarchy in NP
• Proving Circuit Lower Bounds in High Uniform Classes
• Title not available (Why is that?)
• Lower bounds: from circuits to QBF proof systems
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)