Separations in proof complexity and TFNP

DOI10.1109/FOCS54457.2022.00111MaRDI QIDQ6942976zbMATH OpenFDO

Authors Alexandros Hollender, William Pires, Ran Tao, Robert Robere, Siddhartha Jain, Mika Göös

Publication date 15 August 2025

Full work available at URL https://doi.org/10.1109/FOCS54457.2022.00111

Mathematics Subject Classification ID

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

Cited in

(10)

• Bounds on the total coefficient size of nullstellensatz proofs of the pigeonhole principle
• Two choices are enough for P-LCPs, USOs, and colorful tangents
• An FPT algorithm for splitting a necklace among two thieves
• Total NP search problems with abundant solutions
• Intersection classes in TFNP and proof complexity
• TFNP intersections through the Lens of feasible disjunction
• Proving unsatisfiability with hitting formulas
• The computational complexity of finding stationary points in non-convex optimization
• An FPT algorithm for splitting a necklace among two thieves
• Strength and limitations of Sherali-Adams and nullstellensatz proof systems

This page was built for publication: Separations in proof complexity and TFNP

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