Stasys Jukna

Tropical circuits are circuits with Min and Plus, or Max and Plus operations as gates. Their importance stems from their intimate relation to dynamic programming algorithms. The power of tropical circuits lies somewhere between that of monotone boolean circuits and monotone arithmetic circuits. In this paper we present some lower ... more >>>

Stasys Jukna, Hannes Seiwert

Many dynamic programming algorithms are ``pure'' in that they only use min or max and addition operations in their recursion equations. The well known greedy algorithm of Kruskal solves the minimum weight spanning tree problem on $n$-vertex graphs using only $O(n^2\log n)$ operations. We prove that any pure DP algorithm ... more >>>

Stasys Jukna

We consider probabilistic circuits working over the real numbers, and using arbitrary semialgebraic functions of bounded description complexity as gates. We show that such circuits can be simulated by deterministic circuits with an only polynomial blowup in size. An algorithmic consequence is that randomization cannot substantially speed up dynamic programming. ... more >>>

Stasys Jukna, Hannes Seiwert

We develop general lower bound arguments for approximating tropical

(min,+) and (max,+) circuits, and use them to prove the

first non-trivial, even super-polynomial, lower bounds on the size

of such circuits approximating some explicit optimization

problems. In particular, these bounds show that the approximation

powers of pure dynamic programming algorithms ...
more >>>

Stasys Jukna, Hannes Seiwert, Igor Sergeev

It is known that the size of monotone arithmetic $(+,\ast)$ circuits can be exponentially decreased by allowing just one division "at the very end," at the output gate. A natural question is: can the size of $(+,\ast)$ circuits be substantially reduced if we allow divisions "at the very beginning," that ... more >>>

Stasys Jukna

A monotone Boolean $(\lor,\land)$ circuit $F$ computing a Boolean function $f$ is a read-$k$ circuit if the polynomial produced (purely syntactically) by the arithmetic $(+,\times)$ version of $F$ has the property that for every prime implicant of $f$, the polynomial contains a monomial with the same set of variables, each ... more >>>