All reports by Author Stasys Jukna:

__
TR20-102
| 9th July 2020
__

Stasys Jukna#### Notes on Hazard-Free Circuits

Revisions: 1

__
TR19-158
| 11th November 2019
__

Stasys Jukna, Hannes Seiwert#### Sorting Can Exponentially Speed Up Pure Dynamic Programming

__
TR18-154
| 7th September 2018
__

Stasys Jukna, Andrzej Lingas#### Lower Bounds for Circuits of Bounded Negation Width

__
TR18-127
| 9th July 2018
__

Stasys Jukna, Hannes Seiwert#### Approximation Limitations of Tropical Circuits

__
TR18-051
| 15th March 2018
__

Stasys Jukna#### Derandomizing Dynamic Programming and Beyond

Revisions: 1

__
TR18-049
| 14th March 2018
__

Stasys Jukna, Hannes Seiwert#### Greedy can also beat pure dynamic programming

Revisions: 1

__
TR18-042
| 1st March 2018
__

Stasys Jukna#### Incremental versus Non-Incremental Dynamic Programming

__
TR16-123
| 11th August 2016
__

Stasys Jukna#### Tropical Complexity, Sidon Sets, and Dynamic Programming

__
TR15-127
| 7th August 2015
__

Stasys Jukna, Georg Schnitger#### On the Optimality of Bellman--Ford--Moore Shortest Path Algorithm

Revisions: 1

__
TR14-169
| 9th December 2014
__

Stasys Jukna#### Lower Bounds for Monotone Counting Circuits

__
TR14-080
| 11th June 2014
__

Stasys Jukna#### Lower Bounds for Tropical Circuits and Dynamic Programs

Revisions: 1

__
TR12-041
| 17th April 2012
__

Stasys Jukna#### Limitations of Incremental Dynamic Programs

Revisions: 1

__
TR12-039
| 17th April 2012
__

Stasys Jukna#### Clique Problem, Cutting Plane Proofs, and Communication Complexity

__
TR09-040
| 20th April 2009
__

Pavel Hrubes, Stasys Jukna, Alexander Kulikov, Pavel Pudlak#### On convex complexity measures

__
TR09-008
| 15th January 2009
__

Stasys Jukna, Georg Schnitger#### Min-Rank Conjecture for Log-Depth Circuits

__
TR08-019
| 6th March 2008
__

Stasys Jukna#### Entropy of operators or why matrix multiplication is hard for small depth circuits

Revisions: 1

__
TR05-079
| 25th July 2005
__

Stasys Jukna#### Expanders and time-restricted branching programs

__
TR05-021
| 14th February 2005
__

Stasys Jukna#### Disproving the single level conjecture

Revisions: 2
,
Comments: 1

__
TR04-062
| 28th July 2004
__

Stasys Jukna#### A note on the P versus NP intersected with co-NP question in communication complexity

Revisions: 1
,
Comments: 1

__
TR04-005
| 19th January 2004
__

Stasys Jukna#### On Graph Complexity

Revisions: 1
,
Comments: 1

__
TR01-066
| 28th September 2001
__

Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger#### On Multipartition Communication Complexity

__
TR01-058
| 28th August 2001
__

Stasys Jukna#### A Note on the Minimum Number of Negations Leading to Superpolynomial Savings

__
TR01-049
| 11th July 2001
__

Stasys Jukna, Georg Schnitger#### On Multi-Partition Communication Complexity of Triangle-Freeness

Comments: 2

__
TR01-039
| 18th May 2001
__

Stasys Jukna, Stanislav Zak#### On Uncertainty versus Size in Branching Programs

Revisions: 1

__
TR98-041
| 27th July 1998
__

Stasys Jukna#### Combinatorics of Monotone Computations

__
TR98-030
| 9th June 1998
__

Stasys Jukna, Stanislav Zak#### On Branching Programs With Bounded Uncertainty

__
TR97-007
| 21st February 1997
__

Stasys Jukna#### Exponential Lower Bounds for Semantic Resolution

__
TR96-037
| 14th June 1996
__

Stasys Jukna, Alexander Razborov#### Neither Reading Few Bits Twice nor Reading Illegally Helps Much

__
TR96-026
| 25th March 1996
__

Stasys Jukna#### Finite Limits and Monotone Computations

Revisions: 1
,
Comments: 1

__
TR95-044
| 18th September 1995
__

Carsten Damm, Stasys Jukna, Jiri Sgall#### Some Bounds on Multiparty Communication Complexity of Pointer Jumping

__
TR94-027
| 12th December 1994
__

Stasys Jukna#### A Note on Read-k Times Branching Programs

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. Recently, Ikenmeyer et al. [J. ACM, 66:4 (2019), Article 25] have shown that the hazard-free circuit complexity of any Boolean function $f(x)$ is lower-bounded by the ... more >>>

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 that they only perform basic operations, as $\min$, $\max$, $+$, but no conditional branchings via if-then-else in their recursion equations. It is known that any ... more >>>

Stasys Jukna, Andrzej Lingas

We consider Boolean circuits over $\{\lor,\land,\neg\}$ with negations applied only to input variables. To measure the ``amount of negation'' in such circuits, we introduce the concept of their ``negation width.'' In particular, a circuit computing a monotone Boolean function $f(x_1,\ldots,x_n)$ has negation width $w$ if no nonzero term produced (purely ... 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

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

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

Many dynamic programming algorithms for discrete optimization problems are "pure" in that they only use min/max and addition operations in their recursions. Some of them, in particular those for various shortest path problems, are even "incremental" in that one of the inputs to the addition operations is a variable. We ... more >>>

Stasys Jukna

Many dynamic programming algorithms for discrete 0-1 optimization problems are just special (recursively constructed) tropical (min,+) or (max,+) circuits. A problem is homogeneous if all its feasible solutions have the same number of 1s. Jerrum and Snir [JACM 29 (1982), pp. 874-897] proved that tropical circuit complexity of homogeneous problems ... more >>>

Stasys Jukna, Georg Schnitger

We prove a general lower bound on the size of branching programs over any semiring of zero characteristic, including the (min,+) semiring. Using it, we show that the classical dynamic programming algorithm of Bellman, Ford and Moore for the shortest s-t path problem is optimal, if only Min and Sum ... more >>>

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 circuit counts the number of monomials of evaluated to 1 by a given 0-1 input vector (with multiplicities ... more >>>

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

We consider so-called ``incremental'' dynamic programming (DP) algorithms, and are interested in the number of subproblems produced by them. The standard DP algorithm for the n-dimensional Knapsack problem is incremental, and produces nK subproblems, where K is the capacity of the knapsack. We show that any incremental algorithm for this ... more >>>

Stasys Jukna

Motivated by its relation to the length of cutting plane proofs for the Maximum Biclique problem, here we consider the following communication game on a given graph G, known to both players. Let K be the maximal number of vertices in a complete bipartite subgraph of G (which is not ... more >>>

Pavel Hrubes, Stasys Jukna, Alexander Kulikov, Pavel Pudlak

Khrapchenko's classical lower bound $n^2$ on the formula size of the

parity function~$f$ can be interpreted as designing a suitable

measure of subrectangles of the combinatorial rectangle

$f^{-1}(0)\times f^{-1}(1)$. Trying to generalize this approach we

arrived at the concept of \emph{convex measures}. We prove the

more >>>

Stasys Jukna, Georg 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(x), where M is a completion of

A and f:{0,1}^n --> {0,1}^m is an operator, the i-th coordinate ...
more >>>

Stasys Jukna

In this note we consider unbounded fanin depth-2 circuits with arbitrary boolean functions as gates.

We define the entropy of an operator f:{0,1}^n --> {0,1}^m is as the logarithm of the maximum number of vectors distinguishable by at least one special subfunction of f. Then we prove that every ... more >>>

Stasys Jukna

The \emph{replication number} of a branching program is the minimum

number R such that along every accepting computation at most R

variables are tested more than once. Hence 0\leq R\leq n for every

branching program in n variables. The best results so far were

exponential ...
more >>>

Stasys Jukna

We consider the minimal number of AND and OR gates in monotone

circuits for quadratic boolean functions, i.e. disjunctions of

length-$2$ monomials. The single level conjecture claims that

monotone single level circuits, i.e. circuits which have only one

level of AND gates, for quadratic functions ...
more >>>

Stasys Jukna

We consider the P versus NP\cap coNP question for the classical two-party communication protocols: if both a boolean function and its negation have small nondeterministic communication complexity, what is then its deterministic and/or probabilistic communication complexity? In the fixed (worst) partition case this question was answered by Aho, Ullman and ... more >>>

Stasys Jukna

A boolean circuit $f(x_1,\ldots,x_n)$ \emph{represents} a graph $G$

on $n$ vertices if for every input vector $a\in\{0,1\}^n$ with

precisely two $1$'s in, say, positions $i$ and $j$, $f(a)=1$

precisely when $i$ and $j$ are adjacent in $G$; on inputs with more

or less than two ...
more >>>

Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger

We study k-partition communication protocols, an extension

of the standard two-party best-partition model to k input partitions.

The main results are as follows.

1. A strong explicit hierarchy on the degree of

non-obliviousness is established by proving that,

using k+1 partitions instead of k may decrease

the communication complexity from ...
more >>>

Stasys Jukna

In 1957 Markov proved that every circuit in $n$ variables

can be simulated by a circuit with at most $\log(n+1)$ negations.

In 1974 Fischer has shown that this can be done with only

polynomial increase in size.

In this note we observe that some explicit monotone functions ... more >>>

Stasys Jukna, Georg Schnitger

We show that recognizing the $K_3$-freeness and $K_4$-freeness of

graphs is hard, respectively, for two-player nondeterministic

communication protocols with exponentially many partitions and for

nondeterministic (syntactic) read-$s$ times branching programs.

The key ingradient is a generalization of a coloring lemma, due to

Papadimitriou and Sipser, which says that for every ...
more >>>

Stasys Jukna, Stanislav Zak

We propose an information-theoretic approach to proving lower

bounds on the size of branching programs. The argument is based on

Kraft-McMillan type inequalities for the average amount of

uncertainty about (or entropy of) a given input during the various

stages of computation. The uncertainty is measured by the average

more >>>

Stasys Jukna

We consider a general model of monotone circuits, which

we call d-local. In these circuits we allow as gates:

(i) arbitrary monotone Boolean functions whose minterms or

maxterms (or both) have length at most <i>d</i>, and

(ii) arbitrary real-valued non-decreasing functions on ...
more >>>

Stasys Jukna, Stanislav Zak

We propose an information-theoretic approach to proving

lower bounds on the size of branching programs (b.p.). The argument

is based on Kraft-McMillan type inequalities for the average amount of

uncertainty about (or entropy of) a given input during various

stages of the computation. ...
more >>>

Stasys Jukna

In a semantic resolution proof we operate with clauses only

but allow {\em arbitrary} rules of inference:

C_1 C_2 ... C_m

__________________

C

Consistency is the only requirement. We prove a very simple

exponential lower bound for the size ...
more >>>

Stasys Jukna, Alexander Razborov

We first consider so-called {\em $(1,+s)$-branching programs}

in which along every consistent path at most $s$ variables are tested

more than once. We prove that any such program computing a

characteristic function of a linear code $C$ has size at least

more >>>

Stasys Jukna

We prove a general combinatorial lower bound on the

size of monotone circuits. The argument is different from

Razborov's method of approximation, and is based on Sipser's

notion of `finite limit' and Haken's `counting bottlenecks' idea.

We then apply this criterion to the ...
more >>>

Carsten Damm, Stasys Jukna, Jiri Sgall

We introduce the model of conservative one-way multiparty complexity

and prove lower and upper bounds on the complexity of pointer jumping.

The pointer jumping function takes as its input a directed layered

graph with a starting node and layers of nodes, and a single edge ...
more >>>

Stasys Jukna

A syntactic read-k times branching program has the restriction

that no variable occurs more than k times on any path (whether or not

consistent). We exhibit an explicit Boolean function f which cannot

be computed by nondeterministic syntactic read-k times branching programs

of size less than exp(\sqrt{n}}k^{-2k}), ...
more >>>