Lower Bounds for Threshold and Symmetric Functions in Parallel Computation
Yossi Azar · SIAM Journal on Computing · 1992
The family of decision problems of the threshold languages $L_g $ is considered. A threshold language $L_g $ is the set of n bit vectors having at least $g(n)$ “1”s. Using a new technique for controlling the size and structure of a hypergraph by a potential function, lower bounds are proven for these decision problems on a PRIORITY PRAM with m shared memory cells and any polynomial number of processors. The lower bounds are almost tight for the admissible range $(m \leq n^\epsilon )$. By combining these results with the results of Vishkin and Wigderson and the results of Li and Yesha, this paper is able to show a complexity gap between an m cell PRIORITY PRAM having an exponential (or unlimited) number of processors and one having only a polynomial number. A consequence of these results is that PRIORITY PRAM and ARBITRARY PRAM with m shared memory cells and any given polynomial number of processors have the same power (up to a small factor) for computing symmetric functions.