27 citations · 52 across the 11 of their papers we have counts for
12 papers
Notes on Boolean Read-k and Multilinear Circuits
Stasys Jukna
A monotone Boolean (OR,AND) circuit computing a monotone Boolean function f is a read-k circuit if the polynomial produced (purely syntactically) by the arithmetic (+,x) version of…
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…
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…
Lower Bounds for Monotone Counting Circuits
Stasys Jukna
A {+,x}-circuit counts a given multivariate polynomial f, if its values on 0-1 inputs are the same as those of f; on other inputs the circuit may output arbitrary values. Such a ci…
Lower Bounds for Tropical Circuits and Dynamic Programs
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 po…
Clique problem, cutting plane proofs and communication complexity
S. Jukna
Motivated by its relation to the length of cutting plane proofs for the Maximum Biclique problem, we consider the following communication game on a given graph G, known to both pla…
Min-Rank Conjecture for Log-Depth Circuits
S. Jukna, G. Schnitger
A completion of an m-by-n matrix A with entries in {0,1,*} is obtained by setting all *-entries to constants 0 or 1. A system of semi-linear equations over GF(2) has the form Mx=f(…
Circuits with arbitrary gates for random operators
S. Jukna, G. Schnitger
We consider boolean circuits computing n-operators f:{0,1}^n --> {0,1}^n. As gates we allow arbitrary boolean functions; neither fanin nor fanout of gates is restricted. An operato…