9 citations · 13 across the 4 of their papers we have counts for
5 papers
Regular expression length via arithmetic formula complexity
Ehud Cseresnyes, Hannes Seiwert
We prove lower bounds on the length of regular expressions for finite languages by methods from arithmetic circuit complexity. First, we show a reduction: the length of a regular e…
Sorting Can Exponentially Speed Up Pure Dynamic Programming
Stasys Jukna, Hannes Seiwert
Many discrete minimization problems, including various versions of the shortest path problem, can be efficiently solved by dynamic programming (DP) algorithms that are "pure" in th…
Approximation Limitations of Pure Dynamic Programming
Stasys Jukna, Hannes Seiwert
We prove the first, even super-polynomial, lower bounds on the size of tropical (min,+) and (max,+) circuits approximating given optimization problems. Many classical dynamic progr…
Tropical Kirchhoff's Formula and Postoptimality in Matroid Optimization
Stasys Jukna, Hannes Seiwert
Given an assignment of real weights to the ground elements of a matroid, the min-max weight of a ground element is the minimum, over all circuits containing , of the maximum…
Greedy can beat pure dynamic programming
Stasys Jukna, Hannes Seiwert
Many dynamic programming algorithms for discrete 0-1 optimizationproblems are "pure" in that their recursion equations only use min/max and addition operations, and do not depend o…