Lower bounds for tropical circuits and dynamic programs
From MaRDI portal
Publication:493653
DOI10.1007/S00224-014-9574-4zbMATH Open1320.68093arXiv1406.3065OpenAlexW1987315863MaRDI QIDQ493653FDOQ493653
Authors: Stasys Jukna 
Publication date: 4 September 2015
Published in: Theory of Computing Systems (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1406.3065
Recommendations
Dynamic programming (90C39) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- On a routing problem
- A Theorem on Boolean Matrices
- The complexity of partial derivatives
- Complexity of monotone networks for Boolean matrix product
- Monotone switching circuits and Boolean matrix product
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- Ramanujan graphs
- Some remarks on Boolean sums
- On another Boolean matrix
- Boolean function complexity. Advances and frontiers.
- Explicit construction of linear sized tolerant networks
- Negation can be exponentially powerful
- A lower bound on the number of additions in monotone computations
- Some Exact Complexity Results for Straight-Line Computations over Semirings
- The monotone circuit complexity of Boolean functions
- Title not available (Why is that?)
- Fast Parallel Computation of Polynomials Using Few Processors
- Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
- Arithmetic circuits: a survey of recent results and open questions
- A direct version of Shamir and Snir's lower bounds on monotone circuit depth
- Title not available (Why is that?)
- On the depth complexity of formulas
- On the Parallel Evaluation of Multivariate Polynomials
- A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials
- Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
- Lower bounds on monotone complexity of the logical permanent
- Combinatorics of monotone computations
- A method for obtaining efficient lower bounds for monotone complexity
- Ramanujan local systems on graphs
- Expanders and time-restricted branching programs
- On the incompressibility of monotone DNFs
- Monotone Circuits for Connectivity Have Depth (log n)2-o(1)
- Subcubic equivalences between path, matrix, and triangle problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the complexity of calculation of differentials and gradients
- Subtraction-free complexity, cluster transformations, and spanning trees
Cited In (12)
- On the optimality of Bellman-Ford-Moore shortest path algorithm
- Tropical Circuit Complexity
- Title not available (Why is that?)
- 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
- Approximation limitations of pure dynamic programming
Uses Software
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)
