Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse





Separating the communication complexities of MOD m and MOD p circuits


Grolmusz,  Vince
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

There are no locators available
Fulltext (public)

(Any fulltext), 11MB

Supplementary Material (public)
There is no public supplementary material available

Grolmusz, V.(1992). Separating the communication complexities of MOD m and MOD p circuits (MPI-I-92-120). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as:
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$ a composite, non-prime power number. Let us note that using $k$--party protocols with $k\geq p$ is crucial here, since there are depth--2, size--$N$ circuits with MOD $p$ gates with $p>k$, whose $k$--party evaluation needs $\Omega(N)$ bits. 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. It is easy to see that 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\leq 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.