{"id":"e26b1101-bf10-4b52-945b-6b8c39c2cd21","arxiv_id":"2607.11540","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Scalar tropical circuits require 2^Ω(n) plus gates for the Birkhoff and directed spanning-tree polytopes, implying exponential mnnc vs polynomial nnc for directed spanning trees.","lead":"Tropical circuits that also allow multiplication by positive constants still need exponential size to compute max-weight bipartite matchings and directed spanning trees. This yields the first exponential size separation between monotone (input-convex) maxout networks and unrestricted ones for the same convex functions.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The central claims rest on a clean polytopal generalization of the classical tropical decomposition technique. The only place fractional vertices could break the argument is if they allowed a rectangle of intermediate measure to contain more than the claimed fraction of 0-1 vertices; the node-weight lemmas prevent exactly that. The proofs are fully written, the weaker constants are acknowledged, and the neural-network corollaries follow by the standard simulation (Lemma 3.3). No internal inconsistency or missing case is apparent, so the reader's ACCEPT / high-confidence assessment stands.","tokens_in":22135,"tokens_out":540,"duration_ms":5306,"concrete_test":"Independently re-derive the bound |E| ¤ (n-1)^2 - |I|·(n-1-|I|) of Lemma 5.2 for a concrete non-integral rectangle: take X = conv{(½e_{12}+½e_{13}, ½e_{21}+½e_{23})} (so μ_A(X)=2) inside a small n=4 instance of P_DST and verify that no arborescence using both (1,2) and (2,1) can appear in any X+Y ⊆ P_DST. If such an arborescence appears, the structural claim fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader's weakest assumption (Decomposition Lemma 3.5 + measures μ_M / μ_A forcing exponentially small rectangles even with fractional vertices) is the correct load-bearing step, but the paper's proofs appear to secure it. Lemmas 4.1–4.2 and 5.1–5.2 establish that any vertex-realizing rectangle of P_PERM or P_DST still forces constant node weights a* (resp. a*) and a bipartition of the support into I \times J \times I^c \times J^c (or the analogous arc-set restriction |E| ¤ (n-1)^2 - |I|·(n-1-|I|)). Because the measures count only the number of positive node weights of vertices, non-integral points cannot inflate μ beyond |I|; the subsequent counting arguments (Lemmas 4.4, 5.4) therefore remain valid. No hidden integrality assumption or measure-failure under dilation/Minkowski sum is visible.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","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.","tokens_in":22344,"tokens_out":834,"duration_ms":7853,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is ready for acceptance. The only possible editorial concern is that the neural-network corollaries, while correctly derived, occupy a relatively small fraction of the text; if the journal prefers a pure complexity-theory framing the authors could be asked to move the ICNN discussion to a short applications subsection, but this is optional."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This paper does two clean things: it shows that adding positive scalar multiplications does not collapse the classical exponential tropical lower bounds for the Birkhoff polytope and the directed spanning-tree polytope, and it turns that into the first exponential size separation between monotone/input-convex maxout networks and unrestricted ones (nnc(P_DST) is O(n^{3}) while mnnc is 2^Ω(n)).\n\nWhat is new is the polytopal decomposition lemma that survives fractional vertices. They replace the usual degree measure with node-support measures μ_M and μ_A, prove that any vertex-realizing rectangle still forces constant node weights and a restricted support bipartition (or arc set), and then count. The classical Jerrum–Snir / Jukna arguments go through once those structural lemmas are in place. The proofs are self-contained and careful; the weaker constants in the exponents are stated openly.\n\nSoft spots are minor and already flagged by the authors: the constants are worse than the pure tropical ones, undirected trees remain open, and it is still unknown whether nnc of the permanent is polynomial. None of that undercuts the main claims. Citations are appropriate; self-cites are to prior tropical results used as black boxes.\n\nThis is for people who care about tropical/monotone circuit complexity or about the theoretical cost of convexity constraints in neural nets. The math is standard CS theory and looks solid. I would send it to referees without hesitation.","headline":"Solid exponential lower bounds for tropical circuits with positive scalars, plus the first clean mnnc-vs-nnc separation for natural polytopes.","tokens_in":22947,"tokens_out":399,"would_cite":true,"duration_ms":4427,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68Q25","90C27","52B12"],"pacs":[],"model":"grok-4.5","headline":"Scalar multiplications do not shrink tropical circuits for perfect matchings or directed spanning trees; monotone maxout nets stay exponential.","keywords":["tropical circuits","scalar multiplications","Birkhoff polytope","directed spanning trees","maxout networks","input-convex neural networks","extension complexity","circuit lower bounds"],"falsifier":"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.","tokens_in":23031,"feed_emoji":"🧮","tokens_out":601,"duration_ms":5336,"temperature":0.7,"pith_summary":"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.","feed_headline":"Scalars fail to shrink tropical circuits for matchings","feed_subtitle":"Monotone maxout nets stay exponential while ordinary nets compute spanning trees in cubic size","key_machinery":"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.","core_discovery":"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}).","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Scalars fail to shrink tropical circuits for matchings","Scalar gates leave tropical matchings exponentially hard","Exp lower bounds hold for scalar tropical spanning trees","Monotone maxout nets exponential while general nets cubic","Convexity forces exponential size in maxout networks"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Scalars fail to shrink tropical circuits for matchings","Scalar gates leave tropical matchings exponentially hard","Exp lower bounds hold for scalar tropical spanning trees","Monotone maxout nets exponential while general nets cubic","Convexity forces exponential size in maxout networks"]},"model":"grok-4.5","effort":"low","cost_usd":0.006324,"raw_usage":{"total_tokens":1518,"prompt_tokens":648,"num_sources_used":0,"completion_tokens":73,"cost_in_usd_ticks":63240000,"prompt_tokens_details":{"text_tokens":648,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":797,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":648,"tokens_out":73,"duration_ms":8007,"temperature":1.0,"reasoning_tokens":797,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-14T04:52:34.341750+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"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.","supporting_citations":[],"review_version":1}