The Complexity of Parallel Prefix Problems on Small Domains (1995)
Shiva P. Chaudhuri, Jaikumar Radhakrishnan
We show non-trivial lower bounds for several prefix problems in the CRCW PRAM model. The chaining problem is, given a binary input, for each 1 in the input, find the index of the nearest 1 (1) to its...
Lower bounds in parallel computation / (1991)
"Graduate Program in Computer Science."