Why are proof complexity lower bounds hard?

DOI10.1109/FOCS.2019.00080MaRDI QIDQ6944157zbMATH OpenFDO

Authors Ján Pich, Rahul Santhanam

Publication date 12 August 2025

Full work available at URL https://ora.ox.ac.uk/objects/uuid:b038d171-928d-4dfe-abf5-a6fdb03217b2

Mathematics Subject Classification ID

Proceedings, conferences, collections, etc. pertaining to computer science (68-06)

Cited in

(4)

• NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials
• Stretching demi-bits and nondeterministic-secure pseudorandomness
• Towards PNP from extended Frege lower bounds
• Iterated lower bound formulas: a diagonalization-based approach to proof complexity

This page was built for publication: Why are proof complexity lower bounds hard?

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