2 papers
cs.CC2026
Hard CNF Instances for Ideal Proof Systems
Tuomas Hakoniemi, Nutan Limaye, Iddo Tzameret
Since the introduction of the Ideal Proof System (IPS) by Grochow and Pitassi (J. ACM 2018), a substantial body of work has established size lower bounds for IPS and its fragments.…
cs.CC2024
Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
Tuomas Hakoniemi, Nutan Limaye, Iddo Tzameret
Strong algebraic proof systems such as IPS (Ideal Proof System; Grochow-Pitassi [GP18]) offer a general model for deriving polynomials in an ideal and refuting unsatisfiable propos…