Tropical complexity, Sidon sets, and dynamic programming

DOI10.1137/16M1064738MaRDI QIDQ2832574zbMATH OpenOpenAlexFDO

Authors Stasys Jukna

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

zbMATH Keywords

arithmetic circuitscover-free setsdynamic programminglower boundsSidon setstropical circuits

Mathematics Subject Classification ID

Extremal set theory (05D05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Dynamic programming (90C39)

Recommendations

• Lower bounds for tropical circuits and dynamic programs
• Approximation limitations of pure dynamic programming
• Complexity of tropical Schur polynomials
• The complexity of tropical matrix factorization
• Complexity of tropical and MIN-plus linear prevarieties

Cites work

• A complete annotated bibliography of work related to Sidon sequences
• A direct version of Shamir and Snir's lower bounds on monotone circuit depth
• A Dynamic Programming Approach to Sequencing Problems
• A lower bound for monotone arithmetic circuits computing \(0-1\) permanent
• 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 Theorem on Boolean Matrices
• Arithmetic circuits: a survey of recent results and open questions
• Boolean function complexity. Advances and frontiers.
• Complexity of tropical Schur polynomials
• Determination of two vectors from the sum
• Explicit construction of exponential sized families of k-independent sets
• Families of finite sets in which no set is covered by the union of two others
• Homogeneous formulas and symmetric polynomials
• scientific article; zbMATH DE number 3918485 (Why is no real title available?)
• scientific article; zbMATH DE number 4023423 (Why is no real title available?)
• scientific article; zbMATH DE number 4045141 (Why is no real title available?)
• Lower bounds for tropical circuits and dynamic programs
• Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
• Negation can be exponentially powerful
• Nonrandom binary superimposed codes
• Norm-graphs and bipartite Turán numbers
• On \(B_ 2\)-sequences of vectors
• On a Problem of Sidon in Additive Number Theory, and on some Related Problems
• On a routing problem
• On another Boolean matrix
• On the depth complexity of formulas
• On the Parallel Evaluation of Multivariate Polynomials
• Partial derivatives in arithmetic complexity and beyond
• Sidon sets in \(\mathbb N^d\)
• Some Exact Complexity Results for Straight-Line Computations over Semirings

Cited in

(11)

• Incremental versus non-incremental dynamic programming
• Exponential lower bounds on the complexity of a class of dynamic programs for combinatorial optimization problems
• Lower bounds for tropical circuits and dynamic programs
• scientific article; zbMATH DE number 7204408 (Why is no real title available?)
• Approximation limitations of pure dynamic programming
• Regular expression length via arithmetic formula complexity
• Tropical Circuit Complexity
• Notes on Boolean read-k and multilinear circuits
• Complexity of linear operators
• Lower bounds on dynamic programming for maximum weight independent set
• Complexity of tropical Schur polynomials

Describes a project that uses

Uses Software

• Algorithm 97

This page was built for publication: Tropical complexity, Sidon sets, and dynamic programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2832574)