Nonnegative Rank Bounds for the Algebraic Monotone Calculus
cs.CC
Submitted: 2026-10-31
Updated: 2026-10-31
License: http://creativecommons.org/licenses/by/4.0/
The gist: In Hrubes' Algebraic Monotone Calculus a DNF tautology A is proved by a monotone arithmetic circuit computing χ(A)-εχ(1) for some ε>0…
Terminology
Abstract
In Hrubes' Algebraic Monotone Calculus a DNF tautology A is proved by a monotone arithmetic circuit computing χ(A)-εχ(1) for some ε>0, where the coefficient of χ(A) at x σ counts the terms of A satisfied by σ, and χ(1)= product i(x i 0+x i 1). Proof size is circuit size, and ε is existentially quantified, so lower bounds must hold at arbitrarily small ε. 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 Ω(εn) whenever ε=ω(n/n). This cannot reach every ε: at shift 2-Θ(n n) Tseitin acquires polynomial-size depth-three proofs, separating the two fragments exponentially. A constant-size index gadget gives bounds for every ε at least2-Ω(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(n) at every ε. 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.
Sources
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Monotone Complexity of Spanning Tree Polynomial Re-visited
- Beyond the Low-Degree Algorithm: Mixtures of Subcubes and Their Applications
- Explicit Lower Bounds Against $\Omega(n)$-Rounds of Sum-of-Squares
- On the extension complexity of polytopes separating subsets of the Boolean cube
Related papers
- The Proof Analysis Problem for Constant-Depth Frege
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?