Portal de Periódicos da CAPES

Circuits and multi-party protocols

1998; Birkhäuser; Volume: 7; Issue: 1 Linguagem: Inglês

10.1007/pl00001592

1420-8954

Vince Grolmusz,

Optimization and Search Problems

Using multi-party communication techniques, we prove that depth-3 circuits with a threshold gate at the top, arbitrary symmetric gates at the next level, and fan-in k MOD m gates at the bottom need exponential size to compute the k-wise inner product function of Babai, Nisan and Szegedy, where m is an odd positive integer satisfying $ m \equiv k \bmod 2m $ . This is one of the rare lower-bound results involving MOD m gates with non-prime power moduli.¶Exponential gap theorems are also presented between the multi-party communication complexities of closely related functions.