Tropical Circuits with Scalar Multiplication Gates
The study investigates algebraic circuits called scalar tropical circuits (STCs), which use max, plus, and multiplication by a positive constant. The paper proves exponential lower bounds for computing maximum weight directed spanning trees and maximum weight bipartite perfect matchings using these STCs. These results imply an exponential separation between monotone and non-monotone neural networks.