Tropical Circuits with Scalar Multiplication Gates
arXiv:2607.11540
The paper studies tropical circuits that include scalar multiplication gates and proves exponential size lower bounds for computing maximum‑weight directed spanning trees and bipartite perfect matchings, leading to an exponential separation between monotone and non‑monotone maxout neural networks and showing that convexity‑constrained networks may need exponentially more resources.
Abstract
We study tropical circuits with scalar multiplication gates, that is, algebraic circuits whose gates implement , , 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.
23 pages, 5 figures