Tropical Complexity, Sidon Sets, and Dynamic Programming
From MaRDI portal
Publication:2832574
DOI10.1137/16M1064738zbMath1353.68103OpenAlexW2548334940MaRDI QIDQ2832574
Publication date: 11 November 2016
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/16m1064738
Dynamic programming (90C39) Extremal set theory (05D05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Incremental versus non-incremental dynamic programming ⋮ Regular expression length via arithmetic formula complexity ⋮ Unnamed Item ⋮ Approximation Limitations of Pure Dynamic Programming
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lower bounds for tropical circuits and dynamic programs
- Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
- Boolean function complexity. Advances and frontiers.
- Homogeneous formulas and symmetric polynomials
- Complexity of tropical Schur polynomials
- Sidon sets in \(\mathbb N^d\)
- Explicit construction of exponential sized families of k-independent sets
- On another Boolean matrix
- Negation can be exponentially powerful
- Families of finite sets in which no set is covered by the union of two others
- A lower bound on the number of additions in monotone computations
- A lower bound for monotone arithmetic circuits computing \(0-1\) permanent
- A direct version of Shamir and Snir's lower bounds on monotone circuit depth
- On \(B_ 2\)-sequences of vectors
- Norm-graphs and bipartite Turán numbers
- A complete annotated bibliography of work related to Sidon sequences
- Partial Derivatives in Arithmetic Complexity and Beyond
- Arithmetic Circuits: A survey of recent results and open questions
- On a routing problem
- A Dynamic Programming Approach to Sequencing Problems
- On the depth complexity of formulas
- Some Exact Complexity Results for Straight-Line Computations over Semirings
- On the Parallel Evaluation of Multivariate Polynomials
- A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials
- Nonrandom binary superimposed codes
- Determination of two vectors from the sum
- A Theorem on Boolean Matrices
- On a Problem of Sidon in Additive Number Theory, and on some Related Problems
