Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Stasys Jukna:

TR18-154 | 7th September 2018
Stasys Jukna, Andrzej Lingas

Lower Bounds for Circuits of Bounded Negation Width

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 >>>

TR18-127 | 9th July 2018
Stasys Jukna, Hannes Seiwert

Approximation Limitations of Tropical Circuits

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 >>>

TR18-051 | 15th March 2018
Stasys Jukna

Derandomizing Dynamic Programming and Beyond

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 >>>

TR18-049 | 14th March 2018
Stasys Jukna, Hannes Seiwert

Greedy can also beat pure dynamic programming

Revisions: 1

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 >>>

TR18-042 | 1st March 2018
Stasys Jukna

Incremental versus Non-Incremental Dynamic Programming

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 >>>

TR16-123 | 11th August 2016
Stasys Jukna

Tropical Complexity, Sidon Sets, and Dynamic Programming

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 >>>

TR15-127 | 7th August 2015
Stasys Jukna, Georg Schnitger

On the Optimality of Bellman--Ford--Moore Shortest Path Algorithm

Revisions: 1

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 >>>

TR14-169 | 9th December 2014
Stasys Jukna

Lower Bounds for Monotone Counting Circuits

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 >>>

TR14-080 | 11th June 2014
Stasys Jukna

Lower Bounds for Tropical Circuits and Dynamic Programs

Revisions: 1

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 >>>

TR12-041 | 17th April 2012
Stasys Jukna

Limitations of Incremental Dynamic Programs

Revisions: 1

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 >>>

TR12-039 | 17th April 2012
Stasys Jukna

Clique Problem, Cutting Plane Proofs, and Communication Complexity

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 >>>

TR09-040 | 20th April 2009
Pavel Hrubes, Stasys Jukna, Alexander Kulikov, Pavel Pudlak

On convex complexity measures

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 >>>

TR09-008 | 15th January 2009
Stasys Jukna, Georg Schnitger

Min-Rank Conjecture for Log-Depth Circuits

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 >>>

TR08-019 | 6th March 2008
Stasys Jukna

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

Revisions: 1

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 >>>

TR05-079 | 25th July 2005
Stasys Jukna

Expanders and time-restricted branching programs

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 >>>

TR05-021 | 14th February 2005
Stasys Jukna

Disproving the single level conjecture

Revisions: 2 , Comments: 1

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 >>>

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

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 >>>

TR04-005 | 19th January 2004
Stasys Jukna

On Graph Complexity

Revisions: 1 , Comments: 1

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 >>>

TR01-066 | 28th September 2001
Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger

On Multipartition Communication Complexity

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 >>>

TR01-058 | 28th August 2001
Stasys Jukna

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

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 >>>

TR01-049 | 11th July 2001
Stasys Jukna, Georg Schnitger

On Multi-Partition Communication Complexity of Triangle-Freeness

Comments: 2

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 >>>

TR01-039 | 18th May 2001
Stasys Jukna, Stanislav Zak

On Uncertainty versus Size in Branching Programs

Revisions: 1

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 >>>

TR98-041 | 27th July 1998
Stasys Jukna

Combinatorics of Monotone Computations

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 >>>

TR98-030 | 9th June 1998
Stasys Jukna, Stanislav Zak

On Branching Programs With Bounded Uncertainty

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 >>>

TR97-007 | 21st February 1997
Stasys Jukna

Exponential Lower Bounds for Semantic Resolution

In a semantic resolution proof we operate with clauses only
but allow {\em arbitrary} rules of inference:

C_1 C_2 ... C_m

Consistency is the only requirement. We prove a very simple
exponential lower bound for the size ... more >>>

TR96-037 | 14th June 1996
Stasys Jukna, Alexander Razborov

Neither Reading Few Bits Twice nor Reading Illegally Helps Much

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 >>>

TR96-026 | 25th March 1996
Stasys Jukna

Finite Limits and Monotone Computations

Revisions: 1 , Comments: 1

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 >>>

TR95-044 | 18th September 1995
Carsten Damm, Stasys Jukna, Jiri Sgall

Some Bounds on Multiparty Communication Complexity of Pointer Jumping

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 >>>

TR94-027 | 12th December 1994
Stasys Jukna

A Note on Read-k Times Branching Programs

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 >>>

ISSN 1433-8092 | Imprint