Lower bounds for tropical circuits and dynamic programs
From MaRDI portal
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 4008289 (Why is no real title available?)
- scientific article; zbMATH DE number 4045141 (Why is no real title available?)
- scientific article; zbMATH DE number 3999837 (Why is no real title available?)
- scientific article; zbMATH DE number 3311395 (Why is no real title available?)
- A Theorem on Boolean Matrices
- A direct version of Shamir and Snir's lower bounds on monotone circuit depth
- A lower bound on the number of additions in monotone computations
- A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials
- A method for obtaining efficient lower bounds for monotone complexity
- Arithmetic circuits: a survey of recent results and open questions
- Boolean function complexity. Advances and frontiers.
- Combinatorics of monotone computations
- Complexity of monotone networks for Boolean matrix product
- Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
- Expanders and time-restricted branching programs
- Explicit construction of linear sized tolerant networks
- Fast Parallel Computation of Polynomials Using Few Processors
- Lower bounds on monotone complexity of the logical permanent
- Monotone Circuits for Connectivity Have Depth (log n)2-o(1)
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- Monotone switching circuits and Boolean matrix product
- Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
- Negation can be exponentially powerful
- On a routing problem
- On another Boolean matrix
- On the Parallel Evaluation of Multivariate Polynomials
- On the complexity of calculation of differentials and gradients
- On the depth complexity of formulas
- On the incompressibility of monotone DNFs
- Ramanujan graphs
- Ramanujan local systems on graphs
- Some Exact Complexity Results for Straight-Line Computations over Semirings
- Some remarks on Boolean sums
- Subcubic equivalences between path, matrix, and triangle problems
- Subtraction-free complexity, cluster transformations, and spanning trees
- The complexity of partial derivatives
- The monotone circuit complexity of Boolean functions
Cited in
(12)- ReLU neural networks of polynomial size for exact maximum flow computation
- Tropical complexity, Sidon sets, and dynamic programming
- Tropical Circuit Complexity
- Approximation limitations of pure dynamic programming
- scientific article; zbMATH DE number 7204408 (Why is no real title available?)
- Regular expression length via arithmetic formula complexity
- Greedy can beat pure dynamic programming
- Incremental versus non-incremental dynamic programming
- Lower bounds for monotone counting circuits
- Shadows of Newton polytopes
- On the optimality of Bellman-Ford-Moore shortest path algorithm
- Tropical effective primary and dual Nullstellensätze
This page was built for publication: Lower bounds for tropical circuits and dynamic programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q493653)
