Lower bounds for tropical circuits and dynamic programs
From MaRDI portal
(Redirected from Publication:493653)
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)- Approximation limitations of pure dynamic programming
- On the optimality of Bellman-Ford-Moore shortest path algorithm
- Tropical Circuit Complexity
- scientific article; zbMATH DE number 7204408 (Why is no real title available?)
- Tropical effective primary and dual Nullstellensätze
- Regular expression length via arithmetic formula complexity
- Lower bounds for monotone counting circuits
- ReLU neural networks of polynomial size for exact maximum flow computation
- Incremental versus non-incremental dynamic programming
- Greedy can beat pure dynamic programming
- Tropical complexity, Sidon sets, and dynamic programming
- Shadows of Newton polytopes
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)
