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 threshold gate on the top needs either exponential size or exponential weights to com...
详细信息
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 threshold 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). In 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 proof does not use any monotonicity or uniformity assumptions, also works for composite m's, and all of the gates have unbounded fan-in. Our main lemma asserts that functions, computed by depth-2 AND-MOD m circuits have low probabilistic communication complexity. (C) 1998 Elsevier Science B.V. All rights reserved.
Define the MODm-degree of a boolean function F to be the smallest degree of any polynomial P, over the ring of integers modulo m, such that for all 0-1 assignments {Mathematical expression}, {Mathematical expression} ...
详细信息
暂无评论