Tropical Circuits with Scalar Multiplication Gates

• URL: http://arxiv.org/abs/2607.11540v1
• Date: Mon, 13 Jul 2026 13:24:15 GMT
• Title: Tropical Circuits with Scalar Multiplication Gates
• Abstract summary: We study tropical circuits with scalar multiplication circuits that implement $max$, $+$, or multiplication with a positive constant.<n>For such circuits, we prove exponential size bounds for computing maximum weight spanning trees and maximum bipartite weight gates.<n>One conclusion is that neural network models with enforcedity constraints, popularly as neural input gates networks (ICNNs), sometimes need to be exponentially larger than their unrestricted counterparts in order to express the same functions.
• Score: 6.975577102450463
• License: http://creativecommons.org/licenses/by/4.0/
• 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 papers

• Quantifying The Limits of AI Reasoning: Systematic Neural Network Representations of Algorithms [10.292476979020522]
  We present a systematic meta-algorithm that converts essentially any circuit into a feedforward neural network (NN)<n>We show that, on any digital computer, our construction emulates the circuit exactly--no approximation, no rounding, modular overflow included--demonstrating that no reasoning task lies beyond the reach of neural networks.
  arXiv  Detail & Related papers  (2025-08-25T21:55:37Z)
• Compressing multivariate functions with tree tensor networks [0.0]
  One-dimensional tensor networks are increasingly being used as a numerical ansatz for continuum functions. We show how more structured tree tensor networks offer a significantly more efficient ansatz than the commonly used tensor train.
  arXiv  Detail & Related papers  (2024-10-04T16:20:52Z)
• Expressivity of Shallow and Deep Neural Networks for Polynomial Approximation [0.0]
  We establish an exponential lower bound on the complexity of any shallow network approximating the product function over a general compact domain. We also demonstrate this lower bound doesn't apply to normalized Lipschitz monomials over the unit cube.
  arXiv  Detail & Related papers  (2023-03-06T23:01:53Z)
• Exploring the Approximation Capabilities of Multiplicative Neural Networks for Smooth Functions [9.936974568429173]
  We consider two classes of target functions: generalized bandlimited functions and Sobolev-Type balls. Our results demonstrate that multiplicative neural networks can approximate these functions with significantly fewer layers and neurons. These findings suggest that multiplicative gates can outperform standard feed-forward layers and have potential for improving neural network design.
  arXiv  Detail & Related papers  (2023-01-11T17:57:33Z)
• Robust Training and Verification of Implicit Neural Networks: A Non-Euclidean Contractive Approach [64.23331120621118]
  This paper proposes a theoretical and computational framework for training and robustness verification of implicit neural networks. We introduce a related embedded network and show that the embedded network can be used to provide an $ell_infty$-norm box over-approximation of the reachable sets of the original network. We apply our algorithms to train implicit neural networks on the MNIST dataset and compare the robustness of our models with the models trained via existing approaches in the literature.
  arXiv  Detail & Related papers  (2022-08-08T03:13:24Z)
• Variable Bitrate Neural Fields [75.24672452527795]
  We present a dictionary method for compressing feature grids, reducing their memory consumption by up to 100x. We formulate the dictionary optimization as a vector-quantized auto-decoder problem which lets us learn end-to-end discrete neural representations in a space where no direct supervision is available.
  arXiv  Detail & Related papers  (2022-06-15T17:58:34Z)
• The Separation Capacity of Random Neural Networks [78.25060223808936]
  We show that a sufficiently large two-layer ReLU-network with standard Gaussian weights and uniformly distributed biases can solve this problem with high probability. We quantify the relevant structure of the data in terms of a novel notion of mutual complexity.
  arXiv  Detail & Related papers  (2021-07-31T10:25:26Z)
• PAC-learning gains of Turing machines over circuits and neural networks [1.4502611532302039]
  We study the potential gains in sample efficiency that can bring in the principle of minimum description length. We use Turing machines to represent universal models and circuits. We highlight close relationships between classical open problems in Circuit Complexity and the tightness of these.
  arXiv  Detail & Related papers  (2021-03-23T17:03:10Z)
• Neural network approaches to point lattice decoding [6.025026882312586]
  Voronoi-reduced basis is introduced to restrict the space of solutions to a binary set. We count the number of affine pieces in the CPWL decoding function to characterize the complexity of the decoding problem.
  arXiv  Detail & Related papers  (2020-12-13T10:53:34Z)
• Multipole Graph Neural Operator for Parametric Partial Differential Equations [57.90284928158383]
  One of the main challenges in using deep learning-based methods for simulating physical systems is formulating physics-based data. We propose a novel multi-level graph neural network framework that captures interaction at all ranges with only linear complexity. Experiments confirm our multi-graph network learns discretization-invariant solution operators to PDEs and can be evaluated in linear time.
  arXiv  Detail & Related papers  (2020-06-16T21:56:22Z)
• Measuring Model Complexity of Neural Networks with Curve Activation Functions [100.98319505253797]
  We propose the linear approximation neural network (LANN) to approximate a given deep model with curve activation function. We experimentally explore the training process of neural networks and detect overfitting. We find that the $L1$ and $L2$ regularizations suppress the increase of model complexity.
  arXiv  Detail & Related papers  (2020-06-16T07:38:06Z)
• Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networks [70.15611146583068]
  We develop exact representations of training two-layer neural networks with rectified linear units (ReLUs) Our theory utilizes semi-infinite duality and minimum norm regularization.
  arXiv  Detail & Related papers  (2020-02-24T21:32:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.