Score: 0

IPS Lower Bounds for Formulas and Sum of ROABPs

Published: July 13, 2025 | arXiv ID: 2507.09515v1

By: Prerona Chatterjee , Utsab Ghosal , Partha Mukhopadhyay and more

Potential Business Impact:

Makes computer proofs harder to solve.

Business Areas:
Intellectual Property Professional Services

We give new lower bounds for the fragments of the Ideal Proof System (IPS) introduced by Grochow and Pitassi (JACM 2018). The Ideal Proof System is a central topic in algebraic proof complexity developed in the context of Nullstellensatz refutation (Beame, Impagliazzo, Krajicek, Pitassi, Pudlak, FOCS 1994) and simulates Extended Frege efficiently. Our main results are as follows. 1. 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. 2. 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 (Hakoniemi, Limaye, Tzameret, STOC 2024 and Behera, Limaye, Ramanathan, Srinivasan, ICALP 2025). The mult-IPS_{Lin'} lower bound result is obtained by combining the quadratic-size formula lower bound technique of Kalorkoti (SICOMP 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 (CCC 2024).

Page Count
30 pages

Category
Computer Science:
Computational Complexity