SIAM Journal on Computing

The way in which way Kolmogorov complexity and instance complexity affect properties of recursively enumerable (r.e.) sets is studied. The well-known $2\log n$ upper bound on the Kolmogorov complexity of initial segments of r. e. sets is shown to ...

We show that a maximum flow in a network with $n$ vertices can be computed deterministically in $O(n^3/\log n)$ time on a uniform-cost RAM. For dense graphs, this improves the previous best bound of $O(n^3)$.

The bottleneck in our algorithm is a ...

It is shown that for any fixed number of variables, linear-programming problems with $n$ linear inequalities can be solved deterministically by $n$ parallel processors in sublogarithmic time. The parallel time bound (counting only the arithmetic ...

It was shown some years ago that the computation time for many important Boolean functions of $n$ arguments on concurrent-read exclusive-write parallel random-access machines (CREW PRAMs) of unlimited size is at least $arphi (n) \approx 0.72\log_...

Motion planning involving arbitrarily many degrees of freedom is known to be PSPACE-hard. In this paper, we examine the complexity of generalized motion-planning problems for planar mechanisms consisting of independently movable objects. Our ...

Yao proved that in the decision-tree model, the average complexity of the best deterministic algorithm is a lower bound on the complexity of randomized algorithms that solve the same problem. Here it is shown that a similar result does not always ...

We consider the problem of identifying the behavior of an unknown automaton with multiplicity in the field $\Ratviii$ of rational numbers ($\Ratviii$-automaton) from multiplicity and equivalence queries. We provide an algorithm which is polynomial in ...

We consider the following variant of Huffman coding in which the costs of the letters, rather than the probabilities of the words, are nonuniform: ``Given an alphabet of $r$ letters {\em of nonuniform length}, find a minimum-average-length prefix-...

We prove that all of Karp's 21 original $NP$-complete problems have a version that is hard to approximate. These versions are obtained from the original problems by adding essentially the same simple constraint. We further show that these problems ...

In this paper, we give for constant $k$ a linear-time algorithm that, given a graph $G=(V,E)$, determines whether the treewidth of $G$ is at most $k$ and, if so, finds a tree-decomposition of $G$ with treewidth at most $k$. A consequence is that ...

An optimal $O(\log\log n)$-time concurrent-read concurrent-write parallel algorithm for detecting all squares in a string is presented. A tight lower bound shows that over general alphabets, this is the fastest possible optimal algorithm. When $p$ ...

We study a new problem---the wakeup problem---that seems to be fundamental in distributed computing. We present efficient solutions to the problem and show how these solutions can be used to solve the consensus problem, the leader-election problem, ...