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.
Related
- Besov and Triebel--Lizorkin Spaces on Filtered Lie Groups, II: Pointwise Multiplication, Localization, Differences
- Triebel - Lizorkin spaces of dominating mixed smoothness are algebras with respect to pointwise multiplication
- Besov and Triebel-Lizorkin Spaces on Filtered Lie Groups with Polynomial Growth, II: Interpolation, Localization, Pointwise Multiplication
- Symplectic groupoid multiplication and Poisson integrators
- On the Supersingular reduction of Cubic fourfolds with Complex Multiplication
BibTeX
@misc{hertrich2026tropical,
title = {{Tropical Circuits with Scalar Multiplication Gates}},
author = {Christoph Hertrich and Moritz Stargalla},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2607.11540},
eprint = {2607.11540},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.11540},
}
RIS
TY - UNPB
TI - Tropical Circuits with Scalar Multiplication Gates
AU - Christoph Hertrich
AU - Moritz Stargalla
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2607.11540
UR - https://arxiv.org/abs/2607.11540
AB - 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.
ER -