标题： IPS下界对于公式和ROABP之和 显示英文标题

标题： IPS Lower Bounds for Formulas and Sum of ROABPs

摘要： 我们为Grochow和Pitassi（JACM 2018）引入的理想证明系统（IPS）的片段提供了新的下界。 理想证明系统是代数证明复杂性中的核心主题，在Nullstellensatz反驳（Beame, Impagliazzo, Krajicek, Pitassi, Pudlak, FOCS 1994）的背景下发展起来，并能高效模拟扩展Frege。 我们的主要结果如下。 1. mult-IPS_{林}：我们证明了布尔超立方体上子集和公理多项式的多线性反驳的几乎二次大小公式下界。 扩展这一结果，我们得到了一个常数次数目标多项式的几乎匹配的定性陈述。 2. IPS_{林}：在零特征域上，我们证明了子集和公理多项式变体的反驳的指数大小ROABPs之和的下界。 当目标多项式适当修改时，该结果也适用于正特征域。 这种修改受到最近的结果（Hakoniemi, Limaye, Tzameret, STOC 2024 和 Behera, Limaye, Ramanathan, Srinivasan, ICALP 2025）的启发。 mult-IPS_{林}的下界结果是通过将Kalorkoti（SICOMP 1985）的二次大小公式下界技术与一些额外的想法相结合而得到的。 IPS_{林}下界结果的证明技术受到Chatterjee, Kush, Saraf 和 Shpilka（CCC 2024）最近的下界结果的启发。 显示英文摘要

摘要： 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).