Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


Separating the communication complexities of MOD m and MOD p circuits

Grolmusz, Vince

MPI-I-92-120. March 1992, 16 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-92-120.pdfMPI-I-92-120.pdf10301 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  AUTHOR = {Grolmusz, Vince},
  TITLE = {Separating the communication complexities of MOD m and MOD p circuits},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-92-120},
  MONTH = {March},
  YEAR = {1992},
  ISSN = {0946-011X},