27 citations · 52 across the 11 of their papers we have counts for
5 papers · 1 filter
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…
Coin Flipping in Dynamic Programming is Almost Useless
Stasys Jukna
We consider probabilistic circuits working over the real numbers, and using arbitrary semialgebraic functions of bounded description complexity as gates. In particular, such circui…
Notes on Hazard-Free Circuits
Stasys Jukna
The problem of constructing hazard-free Boolean circuits (those avoiding electronic glitches) dates back to the 1940s and is an important problem in circuit design and even in cybe…
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…