Separation Results for Constant-Depth and Multilinear Ideal Proof Systems
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914244769873920 |
|---|---|
| author | Behera, Amik Raj Hansen, Magnus Rahbek Dalgaard Limaye, Nutan Srinivasan, Srikanth |
| author_facet | Behera, Amik Raj Hansen, Magnus Rahbek Dalgaard Limaye, Nutan Srinivasan, Srikanth |
| contents | In this work, we establish separation theorems for several subsystems of the Ideal Proof System (IPS), an algebraic proof system introduced by Grochow and Pitassi (J. ACM, 2018). Separation theorems are well-studied in the context of classical complexity theory, Boolean circuit complexity, and algebraic complexity.
In an important work of Forbes, Shpilka, Tzameret, and Wigderson (ToC, 2021), two proof techniques were introduced to prove lower bounds for subsystems of the IPS, namely the functional method and the multiples method. We use these techniques and obtain the following results.
Hierarchy theorem for constant-depth IPS: Recently, Limaye, Srinivasan, and Tavenas (J. ACM 2025) proved a hierarchy theorem for constant-depth algebraic circuits. We adapt the result and prove a hierarchy theorem for constant-depth $\mathsf{IPS}$. We show that there is an unsatisfiable multilinear instance refutable by a depth-$Δ$ $\mathsf{IPS}$ such that any depth-($Δ/10)$ $\mathsf{IPS}$ refutation for it must have superpolynomial size. This result is proved by building on the multiples method.
Separation theorems for multilinear IPS: In an influential work, Raz (ToC, 2006) unconditionally separated two algebraic complexity classes, namely multilinear $\mathsf{NC}^{1}$ from multilinear $\mathsf{NC}^{2}$. In this work, we prove a similar result for a well-studied fragment of multilinear-$\mathsf{IPS}$.
Specifically, we present an unsatisfiable instance such that its functional refutation, i.e., the unique multilinear polynomial agreeing with the inverse of the polynomial over the Boolean cube, has a small multilinear-$\mathsf{NC}^{2}$ circuit. However, any multilinear-$\mathsf{NC}^{1}$ $\mathsf{IPS}$ refutation ($\mathsf{IPS}_{\mathsf{LIN}}$) for it must have superpolynomial size. This result is proved by building on the functional method. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_06299 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Separation Results for Constant-Depth and Multilinear Ideal Proof Systems Behera, Amik Raj Hansen, Magnus Rahbek Dalgaard Limaye, Nutan Srinivasan, Srikanth Computational Complexity F.1.3 In this work, we establish separation theorems for several subsystems of the Ideal Proof System (IPS), an algebraic proof system introduced by Grochow and Pitassi (J. ACM, 2018). Separation theorems are well-studied in the context of classical complexity theory, Boolean circuit complexity, and algebraic complexity. In an important work of Forbes, Shpilka, Tzameret, and Wigderson (ToC, 2021), two proof techniques were introduced to prove lower bounds for subsystems of the IPS, namely the functional method and the multiples method. We use these techniques and obtain the following results. Hierarchy theorem for constant-depth IPS: Recently, Limaye, Srinivasan, and Tavenas (J. ACM 2025) proved a hierarchy theorem for constant-depth algebraic circuits. We adapt the result and prove a hierarchy theorem for constant-depth $\mathsf{IPS}$. We show that there is an unsatisfiable multilinear instance refutable by a depth-$Δ$ $\mathsf{IPS}$ such that any depth-($Δ/10)$ $\mathsf{IPS}$ refutation for it must have superpolynomial size. This result is proved by building on the multiples method. Separation theorems for multilinear IPS: In an influential work, Raz (ToC, 2006) unconditionally separated two algebraic complexity classes, namely multilinear $\mathsf{NC}^{1}$ from multilinear $\mathsf{NC}^{2}$. In this work, we prove a similar result for a well-studied fragment of multilinear-$\mathsf{IPS}$. Specifically, we present an unsatisfiable instance such that its functional refutation, i.e., the unique multilinear polynomial agreeing with the inverse of the polynomial over the Boolean cube, has a small multilinear-$\mathsf{NC}^{2}$ circuit. However, any multilinear-$\mathsf{NC}^{1}$ $\mathsf{IPS}$ refutation ($\mathsf{IPS}_{\mathsf{LIN}}$) for it must have superpolynomial size. This result is proved by building on the functional method. |
| title | Separation Results for Constant-Depth and Multilinear Ideal Proof Systems |
| topic | Computational Complexity F.1.3 |
| url | https://arxiv.org/abs/2601.06299 |