STOC

How much can an imperfect source of randomness affect an algorithm? We examine several simple questions of this type concerning the long-term behavior of a random walk on a finite graph. In our setup, each step of the random walk a “controller” can, ...

We describe efficient constructions of small probability spaces that approximate the independent distribution for general random variables. Previous work on efficient constructions concentrate on approximations of the independent distribution for the ...

Let a universe of m elements be given, along with a family of subsets of the universe (neighborhoods), each of size at most k. We describe methods for assigning the m elements to points in a small-dimensional vector space (over GF(2)), in such a way ...

We deal with the competitive analysis of algorithms for managing data in a distributed environment. We deal with the file allocation problem ([C], [DF], [ML]), where copies of a file may be stored in the local storage of some subset of processors, ...

We consider the on-line version of the original m-machine scheduling problem: given m machines and n positive real jobs, schedule the n jobs on the m machines so as to minimize the make span, the completion time of the last job. In the on-line version, ...

Given a pattern string, we describe a way to preprocess it. We design a constant-time optimal parallel algorithm for finding all occurences of the (preprocessed) pattern in any given text.

A new probabilistic algorithm for factoring univariate polynomials over finite fields is presented whose asymptotic running time improves upon previous results. To factor a polynomial of degree n over F_q, the algorithm uses O((n² + n log q)•(log n)² log ...

Hyperbolic groups are a rich class of groups frequently encountered in mathematical research, particularly in topology. It has been the focus of intense study by many combinatorial group theorists and topologists recently. We present some computational ...

A base of a permutation group G is a subset B of the permutation domain such that only the identity of G fixes B pointwise. The permutation representations of important classes of groups, including all finite simple groups other than the alternating ...

We consider the problem of deciding whether a given system of quadratic homogeneous equations over the reals has non-trivial solution. We design an approximative algorithm whose complexity is polynomial in the number of variables and exponential in the ...

This paper examines several simple algorithms for routing packets on butterfly networks with bounded queues. We show that for any pure queuing protocol, a routing problem in which each of the N inputs sends a packet to a randomly chosen output requires ...

We present and O(1) slowdown emulation of a fault-free N x N two dimensional mesh with a slack of O(log N log log N) by a faulty mesh of the same size and slack. All components of the faulty mesh, including the memory modules, are assumed to be subject ...

We reconsider the old problem of sorting under partial information, and give polynomial time algorithms for the following tasks.

(1) Given a partial order P, find (adaptively) a sequence of comparisons (questions of the form, “is x < y?”) which sorts (...

Our main result is the demonstration of a Boolean function f with nondeterministic and co-nondeterministic complexities O(log n) and ε-error randomized complexity Ω(log² n), for 0 ≤ ε < 1/2. This is the first separation of this kind for a decision ...

We show that for any fixed k, there is a linear-time algorithm which given a graph G either: (i) finds a cutset X of G with |X| ≤ k such that no component of G–X contains more than 3/4|G–X| vertices, or (ii) determines that for any set X of vertices of ...

In this paper, we consider partitioning a planar graph by removing either nodes or edges. In particular, we consider a cut to be either a set of nodes or edges whose removal divides the graph into two pieces.

We define the balance of a cut as the ratio ...

In the Multiway Cut problem we are given an edge-weighted graph and a subset of the vertices called terminals, and asked for a minimum weight set of edges that separates each terminal from all the others. When the number k of terminals is two, this is ...

An H-decomposition of a graph G = (V,E) is a partition of E into subgraphs isomorphic to H. Given a fixed graph H, the H-decomposition problem is to determine whether an input graph G admits an H-decomposition.

I. Holyer (1980) conjectured that H-...

We are given a transition system implicitly through a compact representation and wish to perform simultaneously reachability analysis and minimization without constructing first the whole system graph. We present an algorithm for this problem that ...

In [Saf88] an exponential determination procedure for Bu¨chi automata was shown, yielding tight bounds for decision procedures of some logics ([EJ88, Saf88, SV89, KT89]). In [SV89] the complexity of determinization and complementation of ω-automata was ...

We give a recursion-theoretic characterization of FP which describes polynomial time computation independently of any externally imposed resource bounds. In particular, this syntactic characterization avoids the explicit size bounds on recursion (and ...

Motivated by problems that arise in computing degrees of belief, we consider the problem of computing asymptotic conditional probabilities for first-order formulas. That is, given first-order formulas φ and θ, we consider the number of structures with ...

In this paper, we address the problem of automatically transforming arbitrary programs written for an ideal parallel machine to run on a completely asynchronous machine. We present a transformation which can be applied to an ideal program such that the ...