Tropical Circuits with Scalar Multiplication Gates
Not on the map. Why?
Abstract (arXiv)
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.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 13 of its 25 references that are in the map. First posted on arXiv 13 Jul 2026.
Builds on
13 of 25 references.
References · 13
- 2016Input Convex Neural Networkscited by 407
- 2019Optimal transport mapping via input convex neural networkscited by 202
- 2023When Deep Learning Meets Polyhedral Theory: A Surveycited by 39
- 2023Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopescited by 36
- 2025On the Expressiveness of Rational ReLU Neural Networks With Bounded Depthcited by 18
- 2020Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Sizecited by 16
- 2021ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computationcited by 11
- 2025Depth-Bounds for Neural Networks via the Braid Arrangementcited by 11
- 2025On the Depth of Monotone ReLU Neural Networks and ICNNscited by 11
- 2025Better Neural Network Expressivity: Subdividing the Simplexcited by 11
- 2022Size and depth of monotone neural networks: interpolation and approximationcited by 10
- 2025Convexity in ReLU Neural Networks: beyond ICNNs?cited by 6
1 more
Built on by
Not cited yet.