Separating the Communication Complexities of MOD m and MOD p Circuits

✍ Scribed by V. Grolmusz

• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 504 KB
• Volume: 51
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1995.1069

✦ Synopsis

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 (\Omega(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 depth2 circuit with MOD (m) gates, but not with any depth-2 circuit with MOD p gates. Obviously, the (k^{\prime})-party protocols are not weaker than the (k)-party protocols, for (k^{\prime}>k). Our results imply that if there is a prime (p) between (k) and (k^{\prime}: k<p \leqslant k^{\prime}), then there exists a function which can be computed by a (k^{\prime})-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. c 1995 Academic Press, Inc.