Pith. sign in

REVIEW 5 minor 10 references

Tropical Circuits with Scalar Multiplication Gates

T0 review · 0 major / 5 minor · reviewed 2026-07-14 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Scalar multiplications do not shrink tropical circuits for perfect matchings or directed spanning trees; monotone maxout nets stay exponential.

desk verdict Solid exponential lower bounds for tropical circuits with positive scalars, plus the first clean mnnc-vs-nnc separation for natural polytopes. read the letter →

arxiv 2607.11540 v1 pith:QNTQRM7A submitted 2026-07-13 cs.CC cs.LGmath.CO

Christoph Hertrich , Moritz Stargalla This is my paper · ORCID
classification cs.CCcs.LGmath.CO MSC 68Q1768Q2590C2752B12
keywords tropicalcircuitsscalarmultiplicationsBirkhoffpolytopedirectedspanningtreesmaxoutnetworksinput-convexneuralextensioncomplexitycircuitlowerbounds
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Tropical circuits compute max-plus expressions and model pure dynamic programs. The paper adds positive scalar multiplications and asks whether they can make those circuits smaller for classic combinatorial problems. It proves they cannot: every scalar tropical circuit computing the support function of the Birkhoff polytope (assignment problem) or of the directed spanning-tree polytope still needs exponentially many plus gates. The same lower bounds transfer to monotone maxout networks and input-convex neural networks, while an unrestricted maxout network can compute the directed spanning-tree function in cubic size. The result therefore shows that enforced convexity constraints can force an exponential blow-up relative to ordinary neural networks.

What carries the argument

A polytopal Decomposition Lemma: any small scalar tropical circuit writes the target polytope as the convex hull of a few Minkowski sums A_i + B_i in which each A_i is simple under a carefully chosen measure; for the two polytopes those simple sums contain only an exponentially small fraction of the vertices.

What would settle it

Exhibit a scalar tropical circuit of size 2^{o(n)} for either the Birkhoff or the directed spanning-tree support function, or prove that no such circuit exists by showing a matching exponential lower bound that accounts for fractional vertices under the same measures.

Watch

Extended reading notes

Core claim

Even after positive scalar multiplications are allowed, every scalar tropical circuit for the support functions of the Birkhoff polytope and of the directed spanning-tree polytope requires 2^Ω(n) plus gates. Consequently the monotone neural-network complexities of both polytopes are exponential, while the unrestricted neural-network complexity of the directed spanning-tree polytope is only O(n^{3}).

Load-bearing premise

The chosen measures still force every Minkowski sum that can appear in a small circuit to contain only an exponentially small fraction of the target vertices, even after fractional points are created by scalar multiplications.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper introduces scalar tropical circuits (STCs): tropical (max,+) circuits augmented by positive scalar multiplications. It proves that any STC computing the support function of the Birkhoff polytope P_PERM (or of the directed spanning-tree polytope P_DST) requires 2^Ω(n) plus gates (Theorems 1.1–1.2). The proofs rest on a polytopal Decomposition Lemma (Lemma 3.5) that writes the target polytope as a convex hull of a small number of Minkowski sums of “simple” polytopes with respect to carefully chosen measures μ_M and μ_A, followed by structural lemmas showing that any vertex-realizing rectangle with intermediate measure contains only an exponentially small fraction of the 0-1 vertices. As corollaries one obtains exponential lower bounds on the monotone neural-network complexity mnnc of both polytopes, while nnc(P_DST) remains O(n^{3}) via tropicalization of a known subtraction-free circuit, yielding the first exponential separation between monotone/input-convex maxout networks and unrestricted ones.

Significance. The work cleanly isolates the power of positive scalar multiplications inside tropical circuits and shows that they do not help for two classical combinatorial polytopes that already possess polynomial extension complexity. The resulting exponential gap between mnnc and nnc for directed spanning trees is the first of its kind and directly answers an open question about the cost of enforced convexity constraints in neural-network models. The Decomposition Lemma and the measure-based counting arguments are reusable tools that strengthen the classical tropical-circuit lower-bound technique of Jerrum–Snir and Jukna. The manuscript is self-contained, the proofs are complete, and the constants in the exponents are explicitly compared with the classical bounds.

minor comments (5)
  1. Page 7 (Outlook): the comparison of the new constants (c≈0.918 for P_PERM, 9/7 for P_DST) with the classical ones of Jerrum–Snir is useful; a short remark whether the same measures can recover the classical constants under the additional restriction to integral vertices would be welcome.
  2. Lemma 3.5: the inductive construction of Φ_{-v} (deletion of scalar gates with no input, contraction of unary max gates) is correct but a bit terse; a one-sentence reminder that the monomial coefficient vectors of the surviving traces are unchanged would help the reader.
  3. Figure 5: the greyed-out gates and the dashed arc that appears after contraction are helpful; labelling the new input gate x_{d+1} more prominently would make the figure self-explanatory.
  4. Proposition 4.5 / 5.5: the O(n 2^n) upper bounds are classical; citing the precise dynamic-programming recurrences already given by Jerrum–Snir (or Jukna) would avoid the impression that they are new.
  5. Throughout: the notation size+(Φ) is introduced early and used consistently; a single sentence in the preliminaries reminding the reader that scalar gates are never counted would eliminate any residual ambiguity.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: lower bounds follow from an independent polytopal decomposition lemma plus combinatorial counting on rectangles of the target 0-1 polytopes.

full rationale

The derivation chain is self-contained combinatorial circuit complexity. The Decomposition Lemma (Lemma 3.5) is proved by induction on circuit size using only the axioms of a measure (subadditivity under Minkowski sum and convex hull, invariance under dilation). The concrete measures μ_M and μ_A are defined directly from node supports of vertices and are verified to be measures (Propositions 4.3, 5.3). The subsequent rectangle lemmas (4.1–4.4, 5.1–5.4) establish structural constraints (constant node weights a*, bipartition of support, arc-set size bound) that hold for any vertex-realizing rectangle inside P_PERM or P_DST, including those with fractional vertices produced by scalar multiplications; the counting arguments then force exponentially many summands. These steps do not define the target size in terms of itself, do not fit parameters to data, and do not import uniqueness or an ansatz from overlapping-author citations. Prior self-citations ([HL24], [HS25], etc.) supply only background definitions (nnc/mnnc) or the known polynomial upper bound for nnc(P_DST) via tropicalization of an external (+,×,/)-circuit; they are not load-bearing for the exponential lower bounds. The paper therefore contains no circular reduction.

Assumptions & free parameters 0 free parameters · 3 assumptions · 2 invented entities

The paper is pure mathematics. No free parameters are fitted. All background facts are standard polyhedral or circuit-complexity statements; the only new objects are the STC model itself and the two problem-specific measures used in the proofs.

assumptions (3)
  • standard math Support functions of polytopes are closed under max, Minkowski sum and positive dilation, and every positively homogeneous convex CPWL function arises this way (standard duality).
    Used throughout Sections 2–3 to interpret STCs geometrically.
  • standard math The Birkhoff polytope and directed spanning-tree polytope admit the classical half-space descriptions with degree and subtour-elimination inequalities.
    Invoked to prove the structural properties of rectangles (Lemmas 4.1–4.2, 5.1–5.2).
  • domain assumption A bias-free monotone rank-k maxout network of size s can be simulated by an STC of size O(ks^{2} + ksd).
    Lemma 3.3; transfers STC lower bounds to mnnc.
invented entities (2)
  • Scalar tropical circuit (STC) independent evidence
    purpose: Model that isolates the effect of positive scalar multiplications without subtraction.
    Defined in Section 2; the central object of study.
  • Measures μ_M and μ_A
    purpose: Quantify simplicity of polytopes so that the decomposition lemma yields exponential lower bounds.
    Introduced in Sections 4 and 5; tailored to force rectangles to cover few vertices.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Tropical Circuits with Scalar Multiplication Gates." pith.science (2026). https://pith.science/paper/QNTQRM7A

@misc{pith2026260711540,
  author       = {Pith},
  title        = {Pith review of: Tropical Circuits with Scalar Multiplication Gates},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QNTQRM7A}},
  note         = {Machine review of arXiv:2607.11540}
}
abstract

We study tropical circuits with scalar multiplication gates, that is, algebraic circuits whose gates implement $\max$, $+$, or multiplication with a positive constant. For such circuits, we prove exponential size lower bounds for computing maximum weight directed spanning trees and maximum weight bipartite perfect matchings. As a corollary, we obtain an exponential size separation between monotone and non-monotone maxout neural networks, which generalize the popularly used ReLU neural networks. One conclusion from this is that neural network models with enforced convexity constraints, such as input-convex neural networks (ICNNs), sometimes need to be exponentially larger than their unrestricted counterparts in order to express the same functions.

Figures

Figures reproduced from arXiv: 2607.11540 by the authors.

Figure 1
Figure 1. Illustration of the duality between a CPWL function and a polytope. [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Circuits in (a) and (b) compute max(3x1 + 2x2 +x3, x1 + 3x3, 2x2 + 3x3). The numbers in the orange scalar gates are the scalars. The trace in (c) corresponds to the monomial 3x1+2x2+x3. v computes the maximum of k affine functions of the outputs of its incoming neighbors δ − v : zv(x) = max i=1,...,k   X u∈δ − v w i uvzu(x) + b i v   , where w i uv ∈ R for i = 1, . . . , k are weights of the arc uv ∈ A and b i v… view at source ↗
Figure 3
Figure 3. Polytopal interpretation of an STC. Below each gate [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: A rank-3 maxout node with three inputs represented as an STC. Orange nodes are scalar [PITH_FULL_IMAGE:figures/full_fig_p011_4.png]
Figure 5
Figure 5. Figure 5: Illustration of circuits in the proof of Lemma 3.5. The STC Φ in (a) computes [PITH_FULL_IMAGE:figures/full_fig_p014_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

10 extracted references · 2 linked inside Pith

  1. [1]

    The monotone circuit complexity of Boolean functions

    [AB87] Noga Alon and Ravi B Boppana. “The monotone circuit complexity of Boolean functions”. In:Combinatorica7.1 (1987), pp. 1–22. [ABMM18] Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. “Understand- ing deep neural networks with rectified linear units”. In:International Conference on Learning Representations

    1987

  2. [2]

    Input convex neural networks

    [AXK17] Brandon Amos, Lei Xu, and J Zico Kolter. “Input convex neural networks”. In: International conference on machine learning. PMLR. 2017, pp. 146–155. [BBHRY25] Egor Bakaev, Florestan Brunck, Christoph Hertrich, Daniel Reichman, and Amir Yehudayoff. “On the depth of monotone ReLU neural networks and ICNNs”. In: arXiv preprint arXiv:2505.06169(2025). ...

    arXiv 2017

  3. [3]

    Negations are powerful even in small depth

    2022, 39:1– 39:21. [CFMSY26] Bruno Cavalar, Th´ eo Bor´ em Fabris, Partha Mukhopadhyay, Srikanth Srinivasan, and Amir Yehudayoff. “Negations are powerful even in small depth”. In:Proceedings of the 58th Annual ACM Symposium on Theory of Computing. 2026, pp. 2071–2082. [CSZ19] Yize Chen, Yuanyuan Shi, and Baosen Zhang. “Optimal control via neural net- work...

    2022

  4. [4]

    Monotone and partially monotone neural networks

    [DV10] Hennie Daniels and Marina Velikova. “Monotone and partially monotone neural networks”. In:IEEE Transactions on Neural Networks21.6 (2010), pp. 906–917. [Edm65] Jack Edmonds. “Paths, trees, and flowers”. In:Canadian Journal of Mathematics 17 (1965), pp. 449–467. [FGK16] Sergey Fomin, Dima Grigoriev, and Gleb Koshevoy. “Subtraction-free complexity, c...

    2010

  5. [5]

    Con- vexity in ReLU neural networks: beyond ICNNs?

    [GMSG25] Anne Gagneux, Mathurin Massias, Emmanuel Soubies, and R´ emi Gribonval. “Con- vexity in ReLU neural networks: beyond ICNNs?” In:Journal of Mathematical Imag- ing and Vision67.4 (2025), p

    2025

  6. [6]

    To- wards lower bounds on the depth of ReLU neural networks

    [HBDS23] Christoph Hertrich, Amitabh Basu, Marco Di Summa, and Martin Skutella. “To- wards lower bounds on the depth of ReLU neural networks”. In:SIAM Journal on Discrete Mathematics37.2 (2023), pp. 997–1029. [HCTC21] Chin-Wei Huang, Ricky TQ Chen, Christos Tsirigotis, and Aaron Courville. “Con- vex potential flows: universal probability distributions wit...

    2023

  7. [7]

    Arithmetic circuits and neural networks for regular matroids

    [HKL26] Christoph Hertrich, Stefan Kober, and Georg Loho. “Arithmetic circuits and neural networks for regular matroids”. In:International Conference on Integer Program- ming and Combinatorial Optimization. Springer. 2026, pp. 394–409. [HL24] Christoph Hertrich and Georg Loho. “Neural networks and (virtual) extended for- mulations”. In:arXiv preprint arXi...

    arXiv 2026

  8. [8]

    Greedy can beat pure dynamic programming

    [JS19] Stasys Jukna and Hannes Seiwert. “Greedy can beat pure dynamic programming”. In:Information Processing Letters142 (2019), pp. 90–95. [JS20] Stasys Jukna and Hannes Seiwert. “Approximation limitations of pure dynamic programming”. In:SIAM Journal on Computing49.1 (2020), pp. 170–205. [JS82] Mark Jerrum and Marc Snir. “Some exact complexity results f...

    2019

Show all 10 references
  1. [9]

    Size and depth of monotone neural networks: interpolation and approximation

    LIPIcs. 2026, 130:1–130:23. [MR25] Dan Mikulincer and Daniel Reichman. “Size and depth of monotone neural networks: interpolation and approximation”. In:IEEE Transactions on Neural Networks and Learning Systems36.4 (2025), pp. 6314–6325. [MTOL20] Ashok Makkuva, Amirhossein Tag...

    2026

  2. [10]

    The matching polytope has exponential extension complexity

    1985, pp. 354–357. [Rot17] Thomas Rothvoss. “The matching polytope has exponential extension complexity”. In:J. ACM64.6 (2017), 41:1–41:19. [RY11] Ran Raz and Amir Yehudayoff. “Multilinear formulas, maximal-partition discrep- ancy and mixed-sources extractors”. In:Journal of C...

    1985

Pith tools

Reviewed July 14, 2026 · model on record in the stance chip above.