|
Abstract : |
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\Gamma N) bits, where p denotes a prime, and m a composite, non-prime power number. As a corollary, for all m, we show a function, computable with a depth--2 circuit with MODm gates, but not with any depth--2 circuit with MOD p gates. Obviously, the k--party protocols are not weaker than the k 0, |
