Iterated lower bound formulas: a diagonalization-based approach to proof complexity

DOI10.1145/3406325.3451010MaRDI QIDQ6086997zbMATH OpenOpenAlexFDO

Authors Rahul Santhanam, Iddo Tzameret

Publication date 14 November 2023

Published in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/10044/1/93966

zbMATH Keywords

algebraic complexitycircuit complexity lower boundsdiagonalizationideal proof systemiterated lower bound formulasproof complexity lower bounds

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Diagonalization strikes back: some recent lower bounds in complexity theory
• Diagonalization in proof complexity
• Proof complexity lower bounds from algebraic circuit complexity
• scientific article; zbMATH DE number 7471587
• Propositional lower bounds: Algorithms and complexity
• scientific article; zbMATH DE number 4059378
• Lower bounds: from circuits to QBF proof systems
• Simplified lower bounds for propositional proofs
• Strong computational lower bounds via parameterized complexity
• A uniform method for proving lower bounds on the computational complexity of logical theories

Cited in

(5)

• Diagonalization in proof complexity
• The Complexity of the Diagonal Problem for Recursion Schemes
• Semialgebraic proofs, IPS lower bounds, and the -conjecture: can a natural number be negative?
• Algebraic proof systems (invited talk)
• Towards PNP from extended Frege lower bounds

This page was built for publication: Iterated lower bound formulas: a diagonalization-based approach to proof complexity

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