Lower Bounds for Tropical Circuits and Dynamic Programs

Abstract

Tropical circuits are circuits with Min and Plus, or Max and Plus operations as gates. Their importance stems from their intimate relation to dynamic programming algorithms. The power of tropical circuits lies somewhere between that of monotone boolean circuits and monotone arithmetic circuits. In this paper we present some lower bounds arguments for tropical circuits, and hence, for dynamic programs.

Corrected reduction to arithmetic circuits (holds only for multilinear polynomials, now Sect. 4). Solved Open Problem 3 about Min/Max gaps (now Lemma 10). Added lower bounds for the depth of tropical circuits (Sect. 15)

Cited by in corpus (5)

• Greedy can beat pure dynamic programming
• Lower Bounds for Monotone Counting Circuits
• Strongly Exponential Separation Between Monotone VP and Monotone VNP
• ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation
• Lower Bounds on Dynamic Programming for Maximum Weight Independent Set