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, size-N circuits with MOD m gates than with MOD p gates by k-party communication protocols: we show a k-party protocol which communicates O(1) bits to evaluate circuits with MOD p gates, while evaluating circuits with MOD m gates needs Ω(N) bits, where p denotes a prime and m denotes a composite, non-prime power number. As a corollary, for all m, we 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 ≤ k′, then there exists a function which can be computed by a k′-party protocol with a constant number of communicated bits, while any k-party protocol needs linearly many bits of communication. This result gives a hierarchy theorem for multi-party protocols.