SEPARATING THE COMMUNICATION COMPLEXITIES OF MOD-M AND MOD-P CIRCUITS

We prove in this paper that it is much harder to evaluate depth-2, siz e-N circuits with MOD m gates than with MOD p gates by k-party communi cation protocols: we show a k-party protocol which communicates 0(1) b its to evaluate circuits with MOD p gates, while evaluating circuits w ith MOD m gates needs Omega(N) bits, where p denotes a prime and m den otes a composite, non-prime power number. As a corollary, for all m, w e show a function, computable with a depth 2 circuit with MOD m gates, but not with any depth-2 circuit with MOD p gates. Obviously, the k'- party protocols are not weaker than the k-party protocols, for k' > k. Our results imply that if there is a prime p between k and k': k < p less than or equal to k', then there exists a function which can be co mputed by a k'-party protocol with a constant number of communicated b its, while any k-party protocol needs linearly many bits of communicat ion. This result gives a hierarchy theorem for multi-party protocols. (C) 1995 Academic Press, Inc.