betaFeedback

WorksComputer Science

Nonnegative Rank Bounds for the Algebraic Monotone Calculus

Abstract

In Hrubes' Algebraic Monotone Calculus a DNF tautology AA is proved by a monotone arithmetic circuit computing χ(A)−εχ(1)χ(A)-εχ(1) for some ε>0ε>0, where the coefficient of χ(A)χ(A) at xσx^σ counts the terms of AA satisfied by σσ, and χ(1)=∏i(xi0+xi1)χ(1)=\prod_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)2^{Ω(εn)} whenever ε=ω(log⁡n/n)ε=ω(\log n/n). This cannot reach every εε: at shift 2−Θ(nlog⁡n)2^{-Θ(n\log n)} Tseitin acquires polynomial-size depth-three proofs, separating the two fragments exponentially. A constant-size index gadget gives bounds for every ε≥2−Ω(n)ε\geq2^{-Ω(n)}, converting a Sherali-Adams degree bound into a size bound. Depth three is essential: Tseitin has monotone proofs of size O(n3)O(n^3) and depth O(log⁡n)O(\log n) at every εε. Beyond depth three we bound the nonnegative rank of a flattening by L2tL^{2^t} for a monotone formula with LL leaves and mixed-product depth tt: 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.

Introduction

In [21] Hrubeš discovered a family of reductions showing that sufficiently strong monotone lower bounds imply unconditional lower bounds for general, non-monotone computation: on arithmetic circuit size, on Boolean circuit size, and — for a proof system whose proofs are monotone circuits and which polynomially simulates Resolution — on proof size. All of them ask for ϵ\epsilon-sensitive lower bounds: one bounds the monotone complexity not of a single hard object but of a perturbation of an easy one, the perturbation governed by a parameter ϵ>0\epsilon>0 tending to 00. In the two instances this paper is concerned with, the arithmetic and the proof-complexity one, the perturbation is a difference

F−ϵ⋅GF-\epsilon\cdot G

with FF alone monotonically easy. They differ in where the hardness resides and in the quantification over ϵ\epsilon: in the arithmetic instance FF is fixed and easy while GG is arbitrary and carries the hardness, and it suffices to have monotone lower bounds along some sequence of ϵ\epsilon tending to 00; in the proof complexity instance both FF and GG are monotone-easy, and the lower bound is required for every ϵ>0\epsilon> 0, since a proof may use any single ϵ\epsilon. We briefly describe the two instances.

General arithmetic circuits. The arithmetic instance of the reduction is [21 Theorem 2.1]: if a polynomial f∈R[x1,…,xn]f \in\mathbb{R}[x_1,\ldots,x_n] of degree dd has an arithmetic circuit of size ss, then for every sufficiently small ϵ>0\epsilon> 0 the polynomial

gϵ:=(x1+⋯+xn+1)d+ϵ⋅fg_\epsilon:= (x_1+\cdots+x_n+1)^d+\epsilon\cdot f

has a monotone arithmetic circuit of size O(sd2+nlog⁡n)O(sd^2+n\log n). This is F−ϵGF-\epsilon G with FF the universal polynomial U:=(x1+⋯+xn+1)dU := (x_1+\cdots+x_n+1)^d and G=−fG=-f an arbitrary, possibly non-monotone polynomial; since UU contains every monomial of degree at most dd with coefficient at least 11, once ϵ\epsilon is small enough for these coefficients to absorb those of ϵf\epsilon f, every coefficient of gϵg_\epsilon is indeed nonnegative, so gϵg_\epsilon is a legitimate monotone target. Up to the factor d2d^2 the reduction is an exact equivalence: the identity f=(gϵ−g0)/ϵf=(g_\epsilon-g_0)/\epsilon turns a monotone circuit for gϵg_\epsilon at any single ϵ>0\epsilon>0 into a general circuit for ff of essentially the same size, so the monotone size of gϵg_\epsilon and the general circuit size of ff coincide for all sufficiently small ϵ\epsilon, up to the factor d2d^2. In particular, monotone lower bounds on gϵig_{\epsilon_i} along any sequence ϵi→0\epsilon_i\to0 yield an unconditional lower bound for ff, one of the ϵi\epsilon_i eventually falling below the relevant threshold; a bound at a single fixed ϵ\epsilon does not suffice, since the easiness of gϵg_\epsilon for easy ff is guaranteed only below an ϵ0\epsilon_0 depending on the coefficients of ff, and ϵ0\epsilon_0 is not known in advance. The identity also shows that the required lower bounds are genuine: if ff is hard, then gϵg_\epsilon is monotone-hard at every ϵ>0\epsilon>0. An equivalent formulation, via the standard observation that every circuit of size ss can be simulated with a single subtraction as f=f+−f−f=f^+-f^- with f±f^\pm monotone of monotone circuit size O(s)O(s): the negative part f−f^- can always be taken to be a scalar multiple of the fixed universal polynomial UU.

The measure ϵ↦size⁡+(gϵ)\epsilon\mapsto\operatorname{size}_+(g_\epsilon) is thus highly discontinuous at ϵ=0\epsilon=0: g0=Ug_0=U has monotone circuits of size O(n+log⁡d)O(n+\log d), yet whenever ff is hard the monotone size of gϵg_\epsilon jumps, for every ϵ>0\epsilon>0, to essentially the general circuit size of ff—an arbitrarily small perturbation of the easy polynomial UU blows up its monotone complexity, and the hardness is created entirely by the ϵ\epsilon-perturbation. This discontinuity is both the power and the price of the approach. The power: it converts a lower bound in the monotone model — a restricted setting in which strong unconditional lower bounds are known — into a lower bound for general arithmetic circuits, where no such techniques exist. The price: most classical monotone lower bound methods are inapplicable here, as they depend only on the set of monomials that occur — the exponential monotone lower bound for the permanent of Jerrum and Snir [23], for instance, is of this kind — but supp⁡(gϵ)=supp⁡(U)\operatorname{supp}(g_\epsilon)=\operatorname{supp}(U) is the full set of monomials of degree at most dd, the support of an easy polynomial. An ϵ\epsilon-sensitive lower bound must therefore be genuinely coefficient-sensitive and, moreover, discontinuous in the coefficients.

Previous ϵ\epsilon-sensitive lower bounds use communication complexity for monotone arithmetic circuits [7, 6] and extend to separations among monotone circuits, branching programs, formulas and bounded-depth formulas [8]. Here we study the tautology encodings arising from AMC.

The proof complexity setting: Algebraic Monotone Calculus. Hrubeš [21] applied the same idea to proof complexity, defining the Algebraic Monotone Calculus (AMC). The lines of AMC are formal inequalities f⪯gf\preceq g between monotone polynomials, meaning that every monomial occurring in ff occurs also in gg, that is, the support containment supp⁡(f)⊆supp⁡(g)\operatorname{supp}(f)\subseteq\operatorname{supp}(g); accordingly the axioms are f⪯ff \preceq f and a⪯ba \preceq b for reals a≥0a \ge0, b>0b > 0, and the rules are transitivity together with compatibility with the two operations, from f1⪯g1f_1 \preceq g_1 and f2⪯g2f_2 \preceq g_2 infer f1∘f2⪯g1∘g2f_1 \circ f_2 \preceq g_1 \circ g_2 for ∘∈{+,×}\circ\in\{+, \times\}. The size of a proof f1⪯g1,…,fm⪯gmf_1 \preceq g_1,\ldots,f_m \preceq g_m is the size of a smallest monotone arithmetic circuit computing all the polynomials f1,g1,…,fm,gmf_1,g_1,\ldots,f_m,g_m simultaneously. Nothing so far mentions ϵ\epsilon: the lines assert only support containment. The parameter enters through the semantics, since supp⁡(f)⊆supp⁡(g)\operatorname{supp}(f) \subseteq\operatorname{supp}(g) holds iff g−ϵ⋅fg-\epsilon\cdot f is monotone for some ϵ>0\epsilon> 0 iff f⪯gf \preceq g is provable. Quantitatively, the AMC proof size of f⪯gf \preceq g equals, up to a constant factor, the minimum size of a monotone circuit computing ff, gg and g−ϵ⋅fg-\epsilon\cdot f simultaneously, over all ϵ>0\epsilon> 0 [21 Proposition 2.6, Theorem 2.7].

For a DNF AA, the coefficient of the set-multilinear monomial xσ=∏ixiσ(i)x^\sigma=\prod_i x_i^{\sigma(i)} in its characteristic polynomial χ(A)\chi(A) counts the terms of AA satisfied by σ\sigma. Here (xi0,xi1)(x_i^0,x_i^1) is the variable pair for the Boolean variable xix_i, while χ(1)=∏i(xi0+xi1)\chi(1)=\prod_i(x_i^0+x_i^1) collects all such monomials, one per assignment; thus AA is a tautology precisely when supp⁡(χ(1))⊆supp⁡(χ(A))\operatorname{supp}(\chi(1)) \subseteq\operatorname{supp}(\chi(A)), and a proof of AA is an AMC proof of χ(1)⪯χ(A)\chi(1) \preceq\chi(A). A proof of size ss gives a monotone circuit of size O(s)O(s) for χ(A)−ϵ⋅χ(1)\chi(A)-\epsilon\cdot\chi(1) for some ϵ>0\epsilon> 0. Conversely, a monotone circuit of size ss for this difference gives a proof of size O(s+mn)O(s+mn), since χ(A)\chi(A) and χ(1)\chi(1) have monotone circuits of size O(mn)O(mn) when AA has mm terms: both are monotone-easy, and all the difficulty is in the perturbation. Thus a lower bound on the AMC complexity of AA reduces to a monotone circuit lower bound for χ(A)−ϵ⋅χ(1)\chi(A)-\epsilon\cdot\chi(1) for all ϵ>0\epsilon> 0. Since χ(A)\chi(A) and χ(1)\chi(1), and hence their difference, have small general arithmetic circuits, such a bound exhibits polynomials χ(A)−ϵ⋅χ(1)\chi(A)-\epsilon\cdot\chi(1) in VP with no polynomial-size monotone circuit. Separations of monotone VP from VP as such are classical [27]; what is demanded here is that the bound hold for every ϵ>0\epsilon> 0, for targets whose support, for every sufficiently small positive ϵ\epsilon, is that of the easy polynomial χ(1)\chi(1).

On the proof side such a bound has unconditional consequences, because AMC is a strong system: it polynomially simulates Resolution — a Resolution refutation with kk lines yields an AMC proof of size O((m+k)n)O((m+k)n) [21 Proposition 5.8] — so an AMC lower bound, and hence a monotone lower bound on χ(A)−ϵ⋅χ(1)\chi(A)-\epsilon\cdot\chi(1) for every ϵ>0\epsilon> 0, implies a Resolution size lower bound. As we show in § 3, considerably more is true already for the weakest fragment considered here: it simulates Sherali–Adams, and therefore Resolution, when size counts displayed conjunctions. A distinctive feature of the proof complexity setting is that here the “positive part” F=χ(A)F=\chi(A) varies with the instance while G=χ(1)G=\chi(1) is fixed, whereas in the circuit-complexity applications of the reduction it is the other way around: FF is a fixed, simple polynomial (such as a power (1+∑ixi)d(1+\sum_i x_i)^d) and the varying, hardness-carrying part is GG. The interest of AMC as a proof system is that it may be much stronger than Resolution, and here the relation to the monotone calculus MLK of Atserias, Galesi and Pudlák [1] is the relevant benchmark. MLK proves implications A→BA \to B between monotone Boolean formulas, and an LK proof of size ss of a monotone sequent can be turned into one containing only monotone formulas, of size sO(log⁡s)s^{O(\log s)} and with polynomially many lines [1]; on monotone sequents MLK therefore quasipolynomially simulates Frege. Replacing ∧,∨\land,\lor in a monotone circuit AA by ×,+\times,+ yields a monotone polynomial FAF_A, and supp⁡(FA)⊆supp⁡(FB)\operatorname{supp}(F_A) \subseteq\operatorname{supp}(F_B) implies that A→BA \to B is a tautology; the converse fails — x∧y→yx \land y \to y is a tautology while supp⁡(Fx∧y)={xy}\operatorname{supp}(F_{x\land y})=\{xy\} and supp⁡(Fy)={y}\operatorname{supp}(F_y)=\{y\} — so AMC is, over such translations, a genuine weakening of MLK: it is blind to the Boolean identities x2=xx^2=x and x≤1x \le1. Hrubeš [21] indicates — as a remark, without proof — how Frege could be reached in principle by restoring exactly these: AMC augmented with the Boolean axioms f⪯1f \preceq1 and f⪯f2f \preceq f^2 simulates MLK. Whether the Boolean axioms actually help, and whether AMC itself polynomially simulates Frege, are open — both under this translation and under the encoding used in the rest of the paper, where a proof of a DNF tautology AA is a proof of χ(1)⪯χ(A)\chi(1) \preceq\chi(A).

References

  1. [1]Albert Atserias, Nicola Galesi, and Pavel Pudlák. Monotone simulations of non-monotone proofs. Journal of Computer and System Sciences, 65(4):626–638, 2002.DOI
  2. [2]Albert Atserias and Tuomas Hakoniemi. Size-degree trade-offs for sums-of-squares and Positivstellensatz proofs. In 34th Computational Complexity Conference (CCC), volume 137 of LIPIcs, pages 24:1–24:20, 2019.arxiv.org/abs/1811.01351
  3. [3]Gábor Braun, Samuel Fiorini, Sebastian Pokutta, and David Steurer. Approximation limits of linear programs (beyond hierarchies). In 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2012.
  4. [4]Gábor Braun and Sebastian Pokutta. The matching polytope does not admit fully-polynomial size relaxation schemes. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 837–846, 2015. Journal version in IEEE Transactions on Information Theory 61(10):5754–5764, 2015.DOI
  5. [5]Siu On Chan, James R. Lee, Prasad Raghavendra, and David Steurer. Approximate constraint satisfaction requires large LP relaxations. Journal of the ACM, 63(4):34:1–34:22, 2016. Conference version in FOCS 2013; preprint arXiv:1309.0563.arxiv.org/abs/1309.0563
  6. [6]Arkadev Chattopadhyay, Rajit Datta, Utsab Ghosal, and Partha Mukhopadhyay. Monotone complexity of spanning tree polynomial re-visited. In 13th Innovations in Theoretical Computer Science Conference (ITCS), volume 215 of LIPIcs, pages 39:1–39:21, 2022. Preprint arXiv:2109.06941.arxiv.org/abs/2109.06941
  7. [7]Arkadev Chattopadhyay, Rajit Datta, and Partha Mukhopadhyay. Lower bounds for monotone arithmetic circuits via communication complexity. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 786–799, 2021.DOI
  8. [8]Arkadev Chattopadhyay, Utsab Ghosal, and Partha Mukhopadhyay. Robustly separating the arithmetic monotone hierarchy via graph inner-product. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), volume 250 of LIPIcs, pages 12:1–12:20, 2022. Preprint ECCC TR22-071.DOI
  9. [9]Sitan Chen and Ankur Moitra. Beyond the low-degree algorithm: Mixtures of subcubes and their applications. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC), 2019. Preprint arXiv:1803.06521.arxiv.org/abs/1803.06521
  10. [10]Stefan S. Dantchev, Abdul Ghani, and Barnaby Martin. Sherali–Adams and the binary encoding of combinatorial principles. In LATIN 2020: Theoretical Informatics, volume 12118 of Lecture Notes in Computer Science. Springer, 2020.arxiv.org/abs/1911.00403
  11. [11]Mateus de Oliveira Oliveira and Pavel Pudlák. Representations of monotone boolean functions by linear programs. In Proceedings of the 32nd Computational Complexity Conference (CCC), volume 79 of LIPIcs, pages 3:1–3:14, 2017. Journal version in ACM Transactions on Computation Theory 11(4):24, 2019.
  12. [12]Jack Edmonds and Ellis L. Johnson. Matching, Euler tours and the Chinese postman. Mathematical Programming, 5:88–124, 1973.DOI
  13. [13]Yuri Faenza, Samuel Fiorini, Roland Grappe, and Hans Raj Tiwary. Extended formulations, nonnegative factorizations, and randomized communication protocols. Mathematical Programming, 153(1):75–94, 2015. Conference version in ISCO 2012.
  14. [14]Yuval Filmus, Meena Mahajan, Gaurav Sood, and Marc Vinyals. MaxSAT resolution and subcube sums. In Theory and Applications of Satisfiability Testing (SAT 2020), volume 12178 of Lecture Notes in Computer Science, pages 295–311. Springer, 2020.DOI
  15. [15]Samuel Fiorini, Serge Massar, Sebastian Pukutta, Hans Raj Tiwary, and Ronald de Wolf. Exponential lower bounds for polytopes in combinatorial optimization. Journal of the ACM, 62(2):17:1–17:23, 2015.arxiv.org/abs/1111.0837
  16. [16]Noah Fleming, Mika Göös, Stefan Grosser, and Robert Robere. On semi-algebraic proofs and algorithms. In 13th Innovations in Theoretical Computer Science Conference (ITCS), volume 215 of LIPIcs, pages 69:1–69:25, 2022.
  17. [17]Mika Göös, Rahul Jain, and Thomas Watson. Extension complexity of independent set polytopes. SIAM Journal on Computing, 47(1):241–269, 2018.
  18. [18]Dima Grigoriev. Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity. Theoretical Computer Science, 259(1–2):613–622, 2001.DOI
  19. [19]Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43(4):439–561, 2006.DOI
  20. [20]Max Hopkins and Ting-Chun Lin. Explicit lower bounds against Ω(n)-rounds of sum-of-squares. Preprint arXiv:2204.11469, 2022. Conference version in FOCS 2022.arxiv.org/abs/2204.11469
  21. [21]Pavel Hrubeš. On ε-sensitive monotone computations. Computational Complexity, 29(2):6, 2020.
  22. [22]Pavel Hrubeš and Navid Talebanfard. On the extension complexity of polytopes separating subsets of the Boolean cube. Discrete & Computational Geometry, 70:268–278, 2023. Preprint arXiv:2105.11996 (2021).arxiv.org/abs/2105.11996
  23. [23]Mark Jerrum and Marc Snir. Some exact complexity results for straight-line computations over semirings. Journal of the ACM, 29(3):874–897, 1982.DOI
  24. [24]Alexander Lubotzky, Ralph Phillips, and Peter Sarnak. Ramanujan graphs. Combinatorica, 8(3):261–277, 1988.
  25. [25]Mark Rhodes. Rank lower bounds for the Sherali–Adams operator. In Computability in Europe (CiE), volume 4497 of Lecture Notes in Computer Science, pages 648–659. Springer, 2007.DOI
  26. [26]Thomas Rothvoß. The matching polytope has exponential extension complexity. Journal of the ACM, 64(6):41:1–41:19, 2017. Conference version in STOC 2014.
  27. [27]Leslie G. Valiant. Negation can be exponentially powerful. Theoretical Computer Science, 12(3):303–314, 1980.
  28. [28]Aaron D. Wyner. The common information of two dependent random variables. IEEE Transactions on Information Theory, 21(2):163–179, 1975.DOI
  29. [29]Mihalis Yannakakis. Expressing combinatorial optimization problems by linear programs. Journal of Computer and System Sciences, 43(3):441–466, 1991.

Paper details

vlnc:W_9rc3xxhr
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents