A LOWER-BOUND FOR DEPTH-3 CIRCUITS WITH MOD M-GATES

We prove that any depth-3 circuit with MOD m gates of unbounded fan-in on the lowest level, AND gates on the second, and a weighted threshol d gate on the top needs either exponential size or exponential weights to compute the inner product of two vectors of length n over GF(2). I n contrast, with n AND gates at the bottom and n single MOD 2 gate at the top one can compute the inner product function. The lower-bound pr oof does not use any monotonicity or uniformity assumptions, also work s for composite m's, and all of the gates have unbounded fan-in. Our m ain lemma asserts that functions, computed by depth-2 AND-MOD m circui ts have low probabilistic communication complexity. (C) 1998 Elsevier Science B.V. All rights reserved.