2026-08-16T15:56:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25103 2025-12-09T15:09:12Z ddc:004 open_access

IPS Lower Bounds for Formulas and Sum of ROABPs Chatterjee, Prerona Ghosal, Utsab Mukhopadhyay, Partha Sinhababu, Amit Ideal Proof System Lower Bound Algebraic Complexity We give new lower bounds for the fragments of the Ideal Proof System (IPS) introduced by Grochow and Pitassi [Joshua A. Grochow and Toniann Pitassi, 2018]. The Ideal Proof System is a central topic in algebraic proof complexity developed in the context of Nullstellensatz refutation [Paul Beame et al., 1994] and simulates Extended Frege efficiently. Our main results are as follows. - mult-IPS_{Lin'}: We prove nearly quadratic-size formula lower bound for multilinear refutation (over the Boolean hypercube) of a variant of the subset-sum axiom polynomial. Extending this, we obtain a nearly matching qualitative statement for a constant degree target polynomial. - IPS_{Lin'}: Over the fields of characteristic zero, we prove exponential-size sum-of-ROABPs lower bound for the refutation of a variant of the subset-sum axiom polynomial. The result also extends over the fields of positive characteristics when the target polynomial is suitably modified. The modification is inspired by the recent results [Tuomas Hakoniemi et al., 2024; Amik Raj Behera et al., 2025]. The mult-IPS_{Lin'} lower bound result is obtained by combining the quadratic-size formula lower bound technique of Kalorkoti [Kalorkoti, 1985] with some additional ideas. The proof technique of IPS_{Lin'} lower bound result is inspired by the recent lower bound result of Chatterjee, Kush, Saraf and Shpilka [Prerona Chatterjee et al., 2024]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Prerona Chatterjee and Utsab Ghosal and Partha Mukhopadhyay and Amit Sinhababu 2025 Is Part Of LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2025.22 urn:nbn:de:0030-drops-251035 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.22 eng https://creativecommons.org/licenses/by/4.0/legalcode