Tight Bounds on Oblivious Chaining.
The chaining problem is defined as follows. Given values The chaining problem appears as a subproblem in many contexts. There are known algorithms that solve the chaining problem on CRCW PRAMs in $O(\alpha(n))$ time, where $\alpha(n)$ is the inverse of Ackerman's function, and is a very slowly growing function. The author studies a  class of algorithms (called oblivious algorithms) for this problem.  A simple oblivious chaining algorithm running in $O(\alpha(n))$ time is presented. More importantly, the optimality of the algorithm is demonstrated by showing a matching lower  bound for oblivious algorithms using $n$ processors. The first  steps toward a lower bound for all chaining algorithms  are also provided by showing that any chaining algorithm that  runs in two steps must use a superlinear number of processors.  The proofs use prefix graphs and  weak superconcentrators.  An interesting connection  between the two is demonstrated and this idea is used to obtain improved bounds on the size of prefix graphs.
Introduction
Consider the following problem called chaining. Given values a 1 ; :::; an ; a
ig. (Define The output can be viewed as
pointers that chain the 1's into a linked list. The chaining problem is a natural problem to consider in
the context of database retreival operations; all the records that satisfy a particular predicate correspond
to the input bits that have value 1. Chaining the 1's then corresponds to making a linked list of these
records for future processing. Apart from this it appears as a subproblem in many contexts and has
been studied before in [16], [17]. Parallel integer sorting [2], [14], parallel merging of integers drawn from
a restricted domain [3], parallel subset compaction [18], [13],[16] and circuits for computing threshold
functions [15] are examples. It is easy to solve the problem in O(n) time using one processor. Using
processors, very fast parallel algorithms exist, with running times close to constant. For this reason,
and because of its simplicity, it is an open question of theoretical interest [3], [16],[17] whether constant
time parallel algorithms exist.
Berkman and Vishkin [4] and independently, Ragde [16] have given parallel algorithms that solve the
chaining problem in O(ff(n)) time using n processors, where ff(n) is the inverse of Ackerman's function,
and is a very slowly growing function. Using algorithms similar to the chaining algorithm, Berkman and
Vishkin [5] give algorithms achieving the same bounds for other problems : the lowest-common-ancestor
problem and a parenthesis matching problem.
We study oblivious algorithms for the chaining problem. Informally, an oblivious algorithm is one in
which the pattern of memory access depends only on n (the size of the problem), and not on the specific
input. This class of algorithms is of interest because the algorithms of Berkman and Vishkin and Ragde
can be modified to be oblivious. We present a simple oblivious algorithm for chaining running in O(ff(n))
time. While the performance bounds are the same as previously known algorithms, our algorithm is
simple and makes use of previously known graph structures. More importantly, we show that for the
class of oblivious algorithms, this is optimal, by proving that an oblivious chaining algorithm using n
processors
time. Since all known algorithms for chaining can be made oblivious, this
gives evidence of a superconstant lower bound for all chaining algorithms.
Chandra, Fortune and Lipton [7] showed that a circuit of bounded depth for the prefix-carry problem
requires superlinear size, implying a superconstant lower bound on depth for circuits with linear size.
Essentially they show that such a circuit must have the structure of a special type of graph called a
prefix graph. They then prove upper and lower bounds on the size of prefix graphs of bounded depth
[6, 7]. We demonstrate a connection between prefix graphs and another family of graphs called
superconcentrators [11]. Using this idea, we present a simple proof that improves the lower bound of [7],
and shows that the construction in [6] is optimal.
Dolev,Dwork, Pippenger and Wigderson [11] showed a lower bound on weak superconcentrators of
bounded depth. Our lower bound for oblivious chaining algorithms is obtained by interpreting such
algorithms as graphs and using the techniques of [11] to analyze their properties. It is worth noting that
there are chaining algorithms whose graphs are not weak superconcentrators, hence the lower bound of
[11] cannot be used directly.
We provide the first steps towards proving a lower bound for all algorithms by showing that any
chaining algorithm that terminates in 2 steps requires a superlinear number of processors. At the time
of submission of this paper, we conjectured that the techniques developed in this paper would be useful
in proving a lower bound for all algorithms. This was indeed the case, as the techniques used here were
recently extended to prove a lower bound for all chaining algorithms in [9].
The model of computation used in this paper is the Concurrent-Read Concurrent-Write Parallel
Random Access Machine (CRCW PRAM). In the COMMON model of CRCW PRAM, all processors
that simultaneously write to the same memory cell must write the same value. In the more powerful
PRIORITY model, each processor has an associated priority and when several processors simultaneously
write to the same memory cell, the highest priority processor succeeds. It has been shown that the
PRIORITY model is strictly stronger that the COMMON model [1]. We show that when considering
oblivious algorithms, both models are equivalent, if the COMMON machine has some extra memory.
Thus, throughout this paper, the algorithms described run on the COMMON model and the lower bound
is proved on the PRIORITY model.
Oblivious computation on PRAMs
The input to an algorithm for chaining consists of a value n (the size of the problem), and n bits (called
the input vector) representing the problem. At any step, each processor computes, based on its actions
so far, a memory address to access and the contents to write (if it is a write step). By an oblivious
algorithm, we mean one where the address accessed is fixed over all input vectors, i.e. it depends only
on the value n. However, whether or not the processor performs any action may depend on the input
vector, for example, when on the fifth write step, p 1 , if it writes always writes to c 15 , but it
may or may not write depending on the input vector. (Our definition of oblivious algorithms coincides
with what is called semi-oblivious in [10].)
It will be convenient to model the computation of an oblivious algorithm on a graph. Given an
algorithm A and an input size n, the directed graph G A;n is defined as follows. The vertices of G A;n
are grouped into levels. Suppose the algorithm solves the chaining problem in k steps. Then the graph
G A;n will consist of 2k of vertices, numbered 0; :::; 2k.
At even levels we will have a vertex for each cell in the memory that is accessed by the algorithm.
These vertices will have the form (c; 2j); 0  j  k and will be called cell vertices (or just cells). At odd
levels we will have a vertex for each processor. These vertices will have the form (p; 2j
and will be called processor vertices (or just processors). Thus there are k levels of processor vertices
of cell vertices.
Edges of G A;n are defined as follows.
input vector, at step j
input vector, at step j
Initially, bit i of the input vector is assumed to be in cell finally, the output value
corresponding to bit i is assumed to be in cell i. We shall refer to vertices (i; 0) as x i and vertices (i; 2k)
as y i .
Let P be the number of processors used by A. The number of cells accessed during the computation
is at most 2kP . There are two kinds of edges in the graph, those adjacent to a processor vertex and
others. Since each processor vertex has degree at most 4, the former are at most 4kP in number. For
each cell accessed during the computation, there are k cell vertices in the graph, one at each even level.
Thus the total number of cell vertices in the graph is 2k 2 P . Since each cell vertex is adjacent to at most
two of the latter type of edge, there are at most 2k 2 P such edges. Hence the number of edges in the
graph is certainly upperbounded by 6k 2 P .
Given an input vector D, of length n, we shall associate with each cell vertex a content and with
each processor vertex a state. The content associated with (c; 2j) is the content of cell c at step j (just
before the (j 1)st read-write step) in the computation of A on input D. The state associated with
is the state of the processor p after the read step of the (j + 1)th read-write step in the same
computation. At any time in the computation, the action of a processor is dependent solely on its state.
Each processor starts with a fixed initial state.
A partial input is one in which each b i 2 f0; 1; \Lambdag. An input vector each
will denote the set of inputs
consistent with B. For a partial input B and a cell vertex (c; 2j) define
content d for some x 2 XB g.
Similarly, for a processor vertex
state e for some x 2 XB g.
We say a (cell or processor) vertex (x; j) is fixed for a partial input B if j SB ((x; j)) j= 1.
2.1 Oblivious COMMON Simulation of Oblivious PRIORITY
Consider the following problem called the leftmost-one problem. Given input
1g. Fich, Ragde and Wigderson [12] show that the leftmost-one problem can
be solved in O(1) time on COMMON using n processors and n memory cells. Their algorithm can be
made oblivious. We shall use this fact to prove the following
Lemma 2.1 Consider an oblivious algorithm that runs on a PRIORITY PRAM with p processors and
memory cells, in k steps. Then there is an oblivious algorithm solving the same problem on a
COMMON PRAM with p processors and M memory cells in O(k) steps.
Proof : It suffices to show that one write step of an oblivious PRIORITY algorithm can be simulated
on an oblivious COMMON machine in O(1) steps. Suppose The PRIORITY machine writes to r cells
denote the set of processors that may write to c i . D i is a fixed set. Note that some of
the processors may choose not to write. It is sufficient for the COMMON machine to find, for each i, the
highest priority processor in D i that chooses to write. This is done by solving a leftmost-one problem
of size j D i j, using j D i j cells, processors from D i , and O(1) time. The space bound follows from the
fact that
Henceforth we shall refer only to PRIORITY algorithms and by the lemma, all the algorithms run on
COMMON with the same time bounds. Note that in general, it is not true that one step of a PRIORITY
algorithm can be simulated by a COMMON algorithm in O(1) steps. Boppana [1] gives an example of
a problem that can be solved in O(1) time on PRIORITY but
logn
loglog n ) time on COMMON.
3 Upper bounds
Ackerman's function is defined as follows:
For a function f let f (1) ne and I k
1. The functions I k are the inverses of the kth level of Ackerman's function, i.e
I k ng. I 1 behaves like log n and I 2 like log   n. Define jg.
Berkman and Vishkin [4, 3], and independently, Ragde [16] have given algorithms that solve the
chaining problem on PRIORITY in ck steps using nI k (n) processors, where c is a constant  2. From
these algorithms one can construct an algorithm using O(n) processors that takes O(ff(n)) time. We give
simple oblivious algorithms that solve the problem in 2k steps on PRIORITY using nI k (n) processors.
Though the performance bounds are the same, we feel our algorithm is easier to understand.
A prefix graph of size n is a directed acyclic graph with n vertices called
input vertices and n vertices (y 1 ; :::; yn ) of outdegree 0 called output vertices. The depth of a prefix
graph is the length of the longest path from an input to an output. Prefix graphs have the following
property: there is a directed path from x i to y j. Say a prefix graph is levelled if
the vertices can be partitioned into levels numbered 0; such that every edge is from a level
vertex to a level i vertex, for some i  1. Call such an edge a level i edge. A prefix graph is contiguous
if for any vertex v the inputs from which v is reachable are of the form x It is possible
to construct [6] levelled contiguous prefix graphs of size n and depth 2k such that 8i; 1  i  2k, the
number of level i edges  nI k (n).
The restricted-domain prefix-maxima problem is defined as follows: Given an input a 1 ; :::; an ; a i
ig. We show how to solve this problem using a prefix graph. Initially set the value at vertex
propagate the values at their tails to their heads and
vertices at level i select the largest value propagated to them. It is easy to see that the value at a vertex
is reachable from x j g and thus the value at y
Theorem 3.1 8k  1, there is an oblivious PRIORITY PRAM algorithm using nI k (n) processors that
solves the chaining problem in 2k steps.
show how an oblivious PRIORITY PRAM algorithm can simulate the computation of a
levelled, contiguous prefix graph G. Label the edges of G as follows. Let fx r j r 2 [i; j]g be the set
of input vertices that can reach the vertex at the tail of edge e. Label e with j. Designate a memory
cell m(v) to correspond to each vertex v of G. At step i, allocate a processor p(e) to each level i edge
of G so that for any two edges f such that label(e) ! label(f); p(f) has a higher priority than p(e).
Such an allocation is easy to do. For e, an edge from v to w, p(e) reads the value in m(v). If the value
is 0, then p(e) does nothing otherwise it writes the value to m(w). It is easy to show that the value
in m(w) is maxfa r j w is reachable from x r g, and so m(y i To solve the chaining
problem with input a 1 ; :::; an , at first, 1  i  n; simply solve
the restricted-domain prefix-maxima problem with the values in m(x i input. The stated
bounds follow from the bounds on prefix graphs. 2
3.1 Weak Superconcentrators and Prefix Graphs
In [7], it is proved that a prefix graph of depth 2k
edges. We improve the lower
bound, showing that the construction is optimal.
A weak superconcentrator is a directed acyclic graph with n vertices
vertices of outdegree 0, and the property that 8k and exist
vertex disjoint paths between fx and fy j1 ; ::; y jk g. The depth of a weak superconcentrator is
the length of the longest directed path in it. It is proved in [11] that a weak superconcentrator of depth
edges.
Theorem 3.2 A prefix graph of depth 2k requires \Omega\Gamma nI k (n)) edges.
We show that every prefix graph is a weak superconcentrator. Let x be the
input and output vertices of a prefix graph G. 8k and there exist paths
from x i m to y i m . If they are not all vertex disjoint, then 9p; q; 1  such that the paths from
to y jp and x i q to y jq have a common vertex. But then there is a path from x i q to y
contradiction. 2
4 Some useful functions and their properties
Following [11], we define the trees T k (l); l  1. T k (l) has all its leaves at depth k and each edge is
labelled with a power of 2. The out-degree of the root is l and the out-degree of every other vertex
is the label of the edge coming into the vertex from its parent. We describe how to construct T k (l),
starting from the root. The edges and vertices of T k (l) will be created in a certain order. We think of
the vertices at a given depth as being arranged from left to right in order of creation. The rule governing
the labelling of edges is: At any depth, the label of the first edge created is 1 and the label of the jth
edge created is twice the maximum of the product of labels on a path starting with the (j \Gamma 1)th edge
created and ending at a leaf.
Initially we are at the root. When we are at a vertex v at depth less than k, and the number of
children of v created so far is less than the label of the edge to v from its parent (or less than l, if v is
the root), then we create a new child of v, label the connecting edge as per the rule, and move to the
new child. If the number of children created so far is equal to the label on the edge to v from its parent,
we move to the parent of v. If v is the root and it already has l children, the construction is complete.
When we are at a vertex at depth k, i.e. a leaf, we simply move back to the parent.
Recall the definition of Ackerman's function from the previous section. In the Appendix, it is shown
that the maximum of the product of the labels on a path in T k (l), from the root to a leaf is at most
sufficiently large. Let H be the set of leaves. For
be the labels on the edges of the path from the root to h, in that order. Then the
following inequalities hold. (1) - (6) are similar to inequalities that were proved before in [11, 8]. We
include their proofs in the Appendix. We shall prove the others here.
y
Fact: Let v be a non leaf node in the tree (T k (l)) and let w be the next node to its right at the same
level. Let c and d be the labels of the edges to v and w from their parent(s) respectively and let e be the
label of the edge from v to the rightmost child of v. Then it is easily seen that e  2 c and d ? e  2 c .
Lemma 4.1 Let c 1 ; :::; c k be the labels on some path from the root to a leaf. Then, 1  i
jHj be the leaves of the tree, from left to right. The lemma clearly holds for the
path to h 1 (all the labels are 1). Assuming the lemma holds for the path to hm we shall show that it
holds for the path to hm+1 .
The paths to hm and hm+1 diverge at some level; call this level r. then c 1 ; :::; c r are common to both
levels. Let c r+1 ; :::; c k and d r+1 ; :::; d k be the remaining labels on the paths to hm and hm+1 respectively.
Note that each of c r+2 ; :::; c k are labels to rightmost children, so by the above Fact, c j+1  2 c j , for
1. By the inductive hypothesis, 8j; 1
j+1 . Since d r+1 ? c r+1 and
c r  c 2
r+1 , we have c r  d 2
j+1 . This completes the proof. 2
Lemma 4.2 There is a function y 0 (k) such that the following holds. Let l; positive integers. Let
Consider the set of paths from the root to a leaf, which have the property
that be the set of vertices they pass through at levels j; :::; k respectively.
2.
be the vertices in S j , from left to right. Consider the path to the leftmost
leaf, among the set of considered paths. This path passes through v 1 . Let the labels on this path be
If c j  log y, then the label of the edge to the vertex to the right of v 1 is at least y, and we are
done. So assume c j ! log y. Then, by Lemma 4.1, 1  i
(log
. Since c 1 :::c k  y, we have c j :::c k  y
(log be the label of
the edge to the vertex to the right of v 1 . We have d
and from the above
Fact, d 3  2
2y
(log
(log 2. 2
Corollary 4.1 (Inequality 7) If y ? y 0 (k);
If y  y 0 (k);
y
Proof : For v a vertex at level j of T k (l), let c 1 (v); :::; c j (v) be the labels on the path from the root
to v, in that order. Then we have
From Lemma 4.2 we have On the other hand, since the labels on successive
edges at the same level increase by at least a factor of two, there can be at most log y  y edges at level
before the label exceeds y. 2
5 The lower bound
Consider the following facts. Theorem 3.1 shows how to obtain an oblivious chaining algorithm whose
graph (as defined in Section 2) is a prefix graph. By Theorem 3.2, every prefix graph is a weak super-
concentrator. A lower bound for weak superconcentrators is known from [11]. Given these facts, it is
tempting to conjecture that the graph of every oblivious chaining algorithm is a prefix graph and thereby
directly obtain a lower bound. However, there are chaining algorithms whose graphs are not weak su-
perconcentrators. As an example, consider an algorithm in which, in the first two steps, processor P 1
reads x 1 and x 2 without writing anywhere. In the next two steps, P 1 writes the values of x 1 and x 2 to
cells z 1 and z 2 respectively. Now the chaining problem is solved for input z
processor ever reading cells x 1 and x 2 again. In the graph of this computation, all paths from x 1 and
must pass through vertex are hence never vertex disjoint. Thus the graph is not a weak
superconcentrator. This simple example generalizes. It is necessary, therefore, to carefully analyze the
structure of the graph of a chaining algorithm.
We now prove that a PRIORITY algorithm that solves the chaining problem with n processors
It suffices to prove the following
Theorem 5.1 For n sufficiently large, any oblivious PRIORITY algorithm that solves a chaining problem
of size n in k steps
processors.
A;n be the graph for algorithm A, which terminates in k read-write steps, and let
be the input and the output vertices of G A;n . Let H be the set of leaves of T k (l)
defined in the previous section, with
. Pick
U , a random subset of [n] by picking each element of [n] independently with probability p(h). Consider
the partial input Fix the values of the input vertices
of G A;n as indicated by B. For a vertex v of G A;n let f v denote the in-degree of v. Let V j denote the
set of vertices at level 2j; 0  j  k. Call a vertex
Consider a high degree vertex (c; 2j) which is not fixed for B, let (p; be the highest priority
processor that writes to (c; 2j), over all inputs consistent with B, i.e. there is a setting for the variables
so that p writes to c at step j. The state of p can be affected only by those input vertices
that can reach (p; 2j \Gamma 1). Modify B and the input vertex settings so that over all inputs consistent with
the new B, (p; fixed value to (c; 2j). Now (c; 2j) is fixed for B, since (p;
override any other processor that writes. If no processor writes to (c; 2j), then modify B by setting, to 0,
all the variables that reach (c; and so is (c; 2j). Call this operation
fixing a vertex.
Carry out the following two step procedure on G A;n .
(A) For j starting at 1 and going up to k \Gamma 1, fix all the high-degree vertices in V j .
starting at 1 and going up to n, set all the input vertices (with value  ) that can
reach y i through low-degree vertices to the value 1, except x i .
We claim that at the end of this procedure all the undefined input vertices are fixed, except possibly
one. To see this, suppose more than one input vertex is undefined. Set all to 1 except the leftmost
undefined input vertex x i . Let this partial input be C. Let x j be the first input vertex to the right of x i
that has the value 1. Clearly, x j exists and was not set in step (B), x i does not reach
low-degree vertices. However, for the two inputs consistent with C, only vertices reachable
from x i through low degree vertices can have different values, since the high degree vertices are fixed.
Hence the state of y j remains fixed over both inputs, an error.
Write EA;B for the expected number of input bits that are set during this process. By the above
argument, EA;B  E(j U 1. We now obtain an upper bound for E A;B .
Note that when fixing all the high-degree vertices in V
Thus, the only variables that affect the contents of v are the undefined variables that can reach v through
low-degree vertices. Hence D v := E(number of inputs set to fix E(number of undefined inputs
that can reach v through low degree vertices When we actually fix
fix the state of the highest priority processor, p, that writes to v, or, if no processor
writes, we fix v 0 , the vertex that represents the same memory cell as v at the previous time step. The
number of inputs fixed is at most the number of inputs that reach either of the two through low-degree
vertices, i.e. at most 2c j
For a high-degree vertex v is at most the minimum of these two quantities, i.e. D v
1]. The expected number of bits set during (A) is the sum of the expected
number of bits set while fixing each high degree vertex, i.e. EA := E(number of bits set during (A))
g. Thus,
EA
We now upper bound EB , the expected number of inputs set during step (B). Let y j be an output
vertex and let reach y j through low-degree vertices and i 2 U; i 6= jg. As before, j S j
processing y j in step B) P(i 2 U and j 2 U ). Since
the events i 2 U and j 2 U are independent and P(i 2 U and j 2 U Hence E( number
of inputs set while processing y j in step (B) As before, EB is the sum,
over all output vertices y of these expectations. So EB
Clearly,
Multiplying both sides by c k (h), summing over h 2 H, and interchanging the order of summation, we
get
g.
Let Z(v; g.
Notice that Y (v; j) is the disjoint union of Z(v; j) and W (v; j). Using this observation and rewriting,
we get
Before simplifying this further, we observe that the sum of the indegrees of all the cell vertices is
bounded by the number of edges and that the number of cell vertices is bounded by 2k 2 P , i.e.
We now separately bound each of the terms of the LHS, which we call (I), (II), and (III) respectively.
(I) can be written as the sum of two terms by separating vertices of degree greater than I k+1 (n) and
others. Thus
Using inequalities (7b) and (D), to bound the first term and (7a) and (C) to bound the second, we find
Using (5) and (C) to simplify (II) we get
Term (III) can be estimated using (4) and (C), yielding
The RHS of Equation 1 can be estimated using (6) and (3) to give
RHS  n I k (n)\Gamma 2n
Thus, rewriting Equation 1 and simplifying yields
6 Nonoblivious lower bounds
The techniques used in the lower bounds for oblivious algorithms may extend to nonoblivious algorithms.
We conjecture similar lower bounds for all algorithms but are able to prove it only for the case 2.
Although the following theorem may be proved using computations similar to those used
in the oblivious case, we use simpler computations that we hope are more illuminating. We associate a
graph GA;B with a nonoblivious algorithm A and partial input B. As before, G A;B will have levels of
vertices 1. The edges are defined by:
vector consistent with B, at step j
vector consistent with B, at step j
to cell c
Note that in this case, we do not have edges from cell vertices to cell vertices.
For v a vertex of GA;B define SB (v) as before.
Theorem 6.1 Any PRIORITY PRAM algorithm that solves the chaining problem in 2 steps requires8 n(log n) 1
processors.
2 be the number of processors used by A. Suppose A terminates in 2 steps.
GA;B consists of 5 levels (numbered 0,.4) of vertices. Let e be the set of edges between
level level i in GA;B . It is easily seen that for any partial input B, j e B;1 j P and j e B;2 j 2P .
is a level 2 vertex with indegree  ig, and d i =j D i j. Then we have
then
so z such that d i 0
and consider the highest priority processor p that has an edge to v. The state of this
processor depends only on one input bit. We set this input bit so that p writes to v. Let B be the partial
input so defined. Clearly j SB (v) is fixed. In this manner, fix all the vertices in D i 0
, and let
C be the partial input obtained by this procedure. The number of bits set in C is at most d i 0
, since,
fixing each vertex in D i 0
involves setting at most one bit.
All the level 2 vertices of G A;C that are not fixed are written to by less than i 0 processors, each in
at most 2 states. The different things that can be written to the vertex are the (at most) two values
that each processor may write, and, in case no processor writes, the (at most) two values that it initially
contained. Hence 8v; j SC ((v; and each processor
reads a vertex that can have at most 2i 0 different values written, the number of states of a processor is
bounded by the product of the two,i.e.
be the output vertices of G A;C . Suppose
bits
set in C. Define l all the bits
between c l j and c m are undefined, y m may have, as its final value, any one of l
l j !m!l j+1
Since
minimization shows that
r
l j !m!l j+1
For e 2 e C;4 , an edge from (p; 3) to (c; 4), let g(e) be the number of different values that p writes to
c over all inputs consistent with C. For any output vertex (y; 4), let e y be the set of edges into (y; 4).
The number of different values that can be written to (y; 4) is bounded by the number of values that
different processors can write via edges in e y plus the number of values it had before (in the case that
no processor writes). Hence SC ((y; 4))
e2ey
For any processor (p; 3), the total number of diferent values it can write over all edges leading out of it
is bounded by S c ((p; 3))  4i 0 . Summing this quantity over all processors gives an upper bound on the
number of diferent values that can be written via edges in e C;4 . Thus
From Equation 4, we get
(j SC ((y
r
l j !m!l j+1
Finally, from Equation 3, we get
Since r  n
2i0(log n)2
, this yields
Conclusion and Open Problems
We have shown that oblivious chaining with n processors is \Theta(ff(n)) time. This leaves open the question
of whether an O(1) time non-oblivious algorithm exists. Recently, Chaudhuri and Radhakrishnan [9]
settled this question, showing an \Omega\Gamma ff(n)) lower bound for any chaining algorithm using O(n) processors.
Using randomization, better performance may be achieved in some situations. Raman [17] gave a
randomized algorithm that runs in O(1) time if the number of 1's in the input is not too large. We
conjecture that for arbitrary inputs, constant-time chaining is not possible, even using randomization.

Acknowledgements

I am grateful to Ravi Boppana for introducing me to the work in [6] and [11], and for many helpful
discussions. I am indebted to Jaikumar Radhakrishnan for the simple proof of the upper bound and for
innumerable insightful comments.



--R

"Optimal Separations Between Concurrent Write Parallel Machines"
"Improved Deterministic Parallel Integer Sorting"
"Some Triply-Logarithmic Parallel Algorithms"
"Recursive Star-Tree Parallel Data Structure"
"Recursive Star-Tree Parallel Data Structure"
"Unbounded Fan-in Circuits and Associative Functions"
"Lower bounds for Constant Depth Circuits for Prefix Problems"
"Tight Bounds on the Chaining Problem"
The Complexity of Parallel Prefix Problems on Small Domains.
Upper and Lower Time Bounds for Parallel Random Access Machines Without Simultaneous Writes.
"Superconcentrators, Generalizers and Generalized Connectors with Limited Depth"
"Simulations Among Concurrent-Write Models of Parallel Computation"
"Counting and Packing in Parallel"
"On Integer Sorting and Parallel Hashing"
"Perfect Hashing, Graph Entropy and Circuit Complexity"
"The Parallel Simplicity of Compaction and Chaining"
"The Power of Collision: Randomized Parallel Algorithms for Chaining and Integer Sorting"
"Subset Selection in Parallel"
--TR
ackerman's function;parallel;superconcentrators;lower bound;prefix graphs;chaining