Lower bounds for tropical circuits and dynamic programs
From MaRDI portal
Publication:493653
DOI10.1007/s00224-014-9574-4zbMath1320.68093arXiv1406.3065OpenAlexW1987315863MaRDI QIDQ493653
Publication date: 4 September 2015
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1406.3065
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (10)
On the optimality of Bellman-Ford-Moore shortest path algorithm ⋮ Greedy can beat pure dynamic programming ⋮ Lower bounds for monotone counting circuits ⋮ Incremental versus non-incremental dynamic programming ⋮ Shadows of Newton polytopes ⋮ ReLU neural networks of polynomial size for exact maximum flow computation ⋮ Tropical effective primary and dual Nullstellensätze ⋮ Regular expression length via arithmetic formula complexity ⋮ Unnamed Item ⋮ Tropical Complexity, Sidon Sets, and Dynamic Programming
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
- Boolean function complexity. Advances and frontiers.
- Lower bounds on monotone complexity of the logical permanent
- The monotone circuit complexity of Boolean functions
- Explicit construction of linear sized tolerant networks
- A method for obtaining efficient lower bounds for monotone complexity
- Ramanujan graphs
- Some remarks on Boolean sums
- On another Boolean matrix
- Negation can be exponentially powerful
- The complexity of partial derivatives
- Complexity of monotone networks for Boolean matrix product
- Monotone switching circuits and Boolean matrix product
- A lower bound on the number of additions in monotone computations
- A direct version of Shamir and Snir's lower bounds on monotone circuit depth
- Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
- Ramanujan local systems on graphs
- Expanders and time-restricted branching programs
- On the incompressibility of monotone DNFs
- Fast Parallel Computation of Polynomials Using Few Processors
- Arithmetic Circuits: A survey of recent results and open questions
- On a routing problem
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- On the depth complexity of formulas
- Some Exact Complexity Results for Straight-Line Computations over Semirings
- On the Parallel Evaluation of Multivariate Polynomials
- Monotone Circuits for Connectivity Have Depth (log n)2-o(1)
- Subcubic Equivalences Between Path, Matrix, and Triangle Problems
- A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials
- On the complexity of calculation of differentials and gradients
- A Theorem on Boolean Matrices
- Combinatorics of monotone computations
- Subtraction-free complexity, cluster transformations, and spanning trees
This page was built for publication: Lower bounds for tropical circuits and dynamic programs
