STOC

The purpose of this paper is to describe a sorting network of size 0(n log n) and depth 0(log n).

A natural way of sorting is through consecutive halvings: determine the upper and lower halves of the set, proceed similarly within the halves, and so on. ...

We give a randomized algorithm that sorts on an N node network with constant valence in 0(log N) time. More particularly the algorithm sorts N items on an N node cube-connected cycles graph and for some constant k for all large enough α it terminates ...

In Borodin-von zur Gathen-Hopcroft[82] the following program is laid out: obtain a “theory package for parallel algebraic computations”, i.e. fast parallel computations for the widely used problems of symbolic manipulation in an algebraic context. In ...

There is a lot of practical and theoretical interest in designing algorithms to process digital pictures. Of particular interest are problems arising when one starts with an nxn array of pixels and stores it, one pixel per processor, in some sort of ...

We construct a one-dimensional array of cellular automata on which arbitrarily large computations can be implemented reliably, even though each automaton at each step makes an error with some constant probability. To compute reliably with unreliable ...

We show that the minimum possible size of an n-superconcentrator with depth 2k≥4 is θ(nλ(k, n)), where λ(k, .) is the inverse of a certain function at the k-th level of the primitive recursive hierarchy. It follows that the minimum possible depth of an ...

We consider the computation of finite semigroups using unbounded fan-in circuits. There are constant-depth, polynomial size circuits for semigroup product iff the semigroup does not contain a nontrivial group as a subset. In the case that the semigroup ...

It is shown that for every k, polynomial-size, depth-k Boolean circuits are more powerful than polynomial-size, depth-(k−1) Boolean circuits. Connections with a problem about Borel sets and other questions are discussed.

We present a Linear Search Algorithm which decides the n-dimensional knapsack problem in n⁴log(n) + 0.(n³) steps. This algorithm works for inputs consisting of n numbers for some arbitrary but fixed integer n. This result solves an open problem posed ...

A topological method is given for obtaining lower bounds for the height of algebraic computation trees, and algebraic decision trees. Using this method we are able to generalize, and present in a uniform and easy way, almost all the known nonlinear ...

Branching programs for the computation of Boolean functions were first studied in the Master's thesis of Masek.⁷ In a rather straightforward manner they generalize the concept of a decision tree to a decision graph.

Let P be a branching program with ...

Many different types of inter-process communication have been examined from a complexity point of view [SP, Y]. We study a new model, in which a collection of processes

P₀, ..., P_k−1

that share information about a set of integers

{a₀, ...,a_k−1},

...

In this paper, new upper and lower bounds are obtained for the number of gates in parallel prefix circuits with minimum depth when the number of inputs is a power of two. In addition, structural information concerning these circuits is described. ...

In this paper we consider monotone Boolean circuits with three alternations, in the order “or”, “and”, “or.” Whenever the number of alternations is limited to a fixed constant the formula and circuit size measures are polynomially related to each other. ...

There are several computational problems that can be formulated as problems of counting the number of objects having a certain property. Valiant [22] has introduced the class #P which includes a variety of counting problems such as counting the number ...

We prove the following lower bounds for on line computation.

1) Simulating two tape nondeterministic machines by one tape machines requires Ω(n log log n) time.

2) Simulating k tape (deterministic) machines by machines with k pushdown stores requires Ω(...

Several papers have recently dealt with techniques for proving area-time lower bounds for VLSI computation by “crossing sequence” methods. A number of natural questions are raised by these definitions.

1.Is the fooling set approach the most powerful way ...

Every high school student knows how to express the roots of a quadratic equation in terms of radicals; what is less well-known is that this solution was found by the Babylonians a millenia and a half before Christ [Ne]. Three thousand years elapsed ...

We show that any group represented by generators that are cycles of bounded degree has O(n²) diameter, i.e., that the longest product of generators required to reach any permutation in the group is O(n²). We also show how such “short” products can be ...

A function f is defined, mapping graphs with n vertices onto graphs with vertex set {1,...,n} . f(X) is isomorphic to X and X is isomorphic to Y iff f(X) = f(Y). For each d, the restriction of f to graphs of valence d is computable in time O(n^τ(d)) for ...

We announce an algebraic approach to the problem of assigning canonical forms to graphs. We compute canonical forms and the associated canonical labelings (or renumberings) in polynomial time for graphs of bounded valence, in moderately exponential, exp(...

Recent work in public-key cryptography has led to the need to generate large random numbers with known factorization.

This paper describes a probabilistic algorithm that produces a random k-bit integer in factored form. Each such number is equally ...

This paper describes an algorithm for the factorization of multivariate polynomials with coefficients in a finite field that is polynomial-time in the degrees of the polynomial to be factored. The algorithm makes use of a new basis reduction algorithm ...

The integer programming problem is: Given m×n and m×l matrices A and b respectively of integers, find whether, there exists an all integer n×l vector x satisfying the m inequalities A×≤b. In settling an important open problem, Lenstra (1981) showed in ...

The two-dimensional Movers' Problem may be stated as follows: Given a set of polygonal obstacles in the plane, and a two-dimensional robot system B, determine whether one can move B from a given placement to another without touching any obstacle, and ...

We discuss the following problem: given n points in the plane (the “sites”), and an arbitrary query point q, find the site that is closest to q. This problem can be solved by constructing the Voronoi diagram of the given sites, and then locating the ...

We use the idea of self-adjusting trees to create new, simple data structures for priority queues (which we call heaps) and search trees. Unlike other efficient implementations of these data structures, self-adjusting trees have no balance condition. ...

This paper presents a linear-time algorithm for the special case of the disjoint set union problem in which the structure of the unions (defined by a “union tree”) is known in advance. The algorithm executes an intermixed sequence of m union and find ...

Data structures are presented for the problem of maintaining a minimum spanning tree on-line under the operation of updating the cost of some edge in the graph. For the case of a general graph, maintaining the data structure and updating the tree are ...

Let S be a set of n points in three-dimensional space. It is shown that one can always find three planes that divide S into eight open regions, of which no seven together contain more than α n points where α is a constant < 1. This result gives rise to ...