Abstract :
The author proves 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: he shows 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 a composite, non-prime power number. As a corollary, for all m, he shows a function, computable with a depth-2 circuit with MOD m gates, but not with any depth-2 circuit with MOD p gates. He proves in the second part that the GIP function by L. Babai et al. (1989) needs exponential size in n when it is computed by some depth-3 circuits, with threshold, symmetric, and MOD m gates
Keywords :
communication complexity; protocols; GIP function; MOD m circuits; MOD p circuits; communication complexities; depth-2; k-party communication protocols; size-N circuits; Circuits; Complexity theory; Computational efficiency; Computer science; Cost function; Galois fields; Game theory; Protocols; Upper bound;