CIRCUITS AND MULTIPARTY PROTOCOLS

Using multi-party communication techniques, we prove that depth-3 circ uits with a threshold gate at the top, arbitrary symmetric gates at th e next level, and fan-in k MODm gates at the bottom need exponential s ize to compute the ii-wise inner product function of Babai, Nisan and Szegedy, where m is an odd positive integer satisfying m = k mod 2m. T his is one of the rare lower-bound results involving MODm gates with n on-prime power moduli. Exponential gap theorems are also presented bet ween the multiparty communication complexities of closely related func tions.