Tight Bounds on Oblivious Chaining

The chaining problem is defined as follows. Given values a 1 ; :::; an ; a i = 0 or 1, 1 i n, compute b 1 ; :::; b n , such that b i = maxfj j a j = 1; j ! ig. (Define maxfg = 0) The chaining problem appears as a subproblem in many contexts. There are algorithms known that solve the chaining problem on CRCW PRAMs in O(ff(n)) time, where ff(n) is the inverse of Ackerman's function, and is a very slowly growing function. We study a class of algorithms (called oblivious algorithms) for this problem. We present a simple oblivious chaining algorithm running in O(ff(n)) time. More importantly, we demonstrate the optimality of the algorithm by showing a matching lower bound for oblivious algorithms using n processors. We also provide the first steps towards a lower bound for all chaining algorithms by showing that any chaining algorithm that runs in two steps must use a superlinear number of processors. Our proofs use prefix graphs and weak superconcentrators. We demonstrate an interestin..