Metraipolis › archive › dc_40caf69afdc7
Nonnegative Rank Bounds for the Algebraic Monotone Calculus — arXiv:2611.01055
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.01055
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T18:59:12.651Z
- SHA-256 of the archived text
0f9a648028896278d10a09002f27d19948fcf44d371c6ea0189bccb6aee734ba- Stable URL of this page
https://metraipolis.com/documento/dc_40caf69afdc7
How to cite
Nonnegative Rank Bounds for the Algebraic Monotone Calculus — arXiv:2611.01055 — arXiv (en), https://arxiv.org/abs/2611.01055 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_40caf69afdc7 (Metraipolis archive dc_40caf69afdc7, sha256 0f9a648028896278d10a09002f27d19948fcf44d371c6ea0189bccb6aee734ba)
BibTeX
@misc{dc40caf69afdc7,
title = {Nonnegative Rank Bounds for the Algebraic Monotone Calculus — arXiv:2611.01055},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.01055},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_40caf69afdc7; sha256 0f9a648028896278d10a09002f27d19948fcf44d371c6ea0189bccb6aee734ba},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.01055. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In Hrubes' Algebraic Monotone Calculus a DNF tautology $A$ is proved by a monotone arithmetic circuit computing $\chi(A)-\epsilon\chi(1)$ for some $\epsilon>0$, where the coefficient of $\chi(A)$ at $x^\sigma$ counts the terms of $A$ satisfied by $\sigma$, and $\chi(1)=\prod_i(x_i^0+x_i^1)$. Proof size is circuit size, and $\epsilon$ is existentially quantified, so lower bounds must hold at arbitrarily small $\epsilon$. We prove lower bounds for bounded-depth fragments by two nonnegative rank measures of the target: monotone tensor rank and the nonnegative rank of a flattening. At depth three a proof is a nonnegative tensor decomposition. Restricting its terms to subcube indicators gives conical juntas, a system polynomially equivalent to Sherali-Adams in twin variables. For arbitrary terms we adapt Rothvoss' hyperplane separation to monotone tensor rank: Tseitin formulas on constant-degree expanders of large girth need proofs of size $2^{\Omega(\epsilon n)}$ whenever $\epsilon=\omega(\log n/n)$. This cannot reach every $\epsilon$: at shift $2^{-\Theta(n\log n)}$ Tseitin acquires polynomial-size depth-three proofs, separating the two fragments exponentially. A constant-size index gadget gives bounds for every $\epsilon\geq2^{-\Omega(n)}$, converting a Sherali-Adams degree bound into a size bound. Depth three is essential: Tseitin has monotone proofs of size $O(n^3)$ and depth $O(\log n)$ at every $\epsilon$. Beyond depth three we bound the nonnegative rank of a flattening by $L^{2^t}$ for a monotone formula with $L$ leaves and mixed-product depth $t$: the largest number of product gates on a root-to-leaf path whose two inputs each meet both sides of the bipartition. Approximate extension complexity then bounds perfect matching and odd factor instances, and planted CSP integrality gaps give an explicit family of planted Tseitin DNFs hard at inverse-polynomial shift.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.CC, nuovi lavori del giorno).
Categorie arXiv: Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2611.01055 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T18:18:37.664Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).