{"id":"arxiv/2607.11540","url":"https://arxiv.org/abs/2607.11540","tags":["cs.CC","cs.LG","math.CO"],"score":0,"title":"Tropical Circuits with Scalar Multiplication Gates","domain":"cs.CC","source":"arxiv","authors":["Christoph Hertrich","Moritz Stargalla"],"reviews":0,"subject":"cs.CC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-13","reactions":{}}