Limits on the power of concurrent-write parallel machines
Paul W. Beame · 1986
We prove lower bounds for the computation of simple functions on generalized versions of parallel random access machines which allow both concurrent reads and concurrent writes.In particular we show that if the number of processors is limited by a polynomial in n then computing the sum of n n-bit integers requires time f2(log n ) and computing the parity of n input bits requires time fl(x/~n ).The latter result, using reductions given by Chandra, Stockmeyer, and Vishkin (1984), implies that a host of problems including sorting or adding n input bits, or multiplying two n/2-bit integers also require time fl(x/~ n ) to compute.