{"ID":6537500,"CreatedAt":"2026-07-14T02:54:43.516908796Z","UpdatedAt":"2026-07-15T03:28:55.185153975Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.11540","arxiv_id":"2607.11540","title":"Tropical Circuits with Scalar Multiplication Gates","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.","short_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 matc...","url_abs":"https://arxiv.org/abs/2607.11540","url_pdf":"https://arxiv.org/pdf/2607.11540v1","authors":"[\"Christoph Hertrich\",\"Moritz Stargalla\"]","published":"2026-07-13T13:24:15Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.LG\",\"math.CO\"]","methods":"[\"Convolutional Neural Network\"]","has_code":false}