On the Size of Depth-Two Threshold Circuits for the Inner Product Mod 2 Function

摘要

In this paper, we study the size of depth-two threshold circuits computing the inner product mod 2 function IP2_n(x_1,...,x_n,y_1,...,y_n) := Σ_i x_i.y_i (mod 2). First, we reveal that IP2_n can be computed by a depth-two threshold circuit of size significantly smaller than a folklore construction of size O(2~n). Namely, we give a construction of such a circuit (denoted by THR o THR circuit) of size O(1.682~n). We also give an upper bound of O(1.899~n) for the case that the weights of the top threshold gale are polynomially bounded (denoted by MAJ o THR circuit). Second, we give new lower bounds on the size of depth-two circuits of some special form; the top gate is an unbounded weight threshold gate and the bottom gates are symmetric gates (denoted by THR o SYM circuit). We show that any such circuit computing IP2_n has size Ω((1.5 - Є)~n) for every constant Є > 0. This improves the previous bound of Ω(2~n~(1/2)) based on the sign-rank method due to Forster et al. [JCSS '02. FSTTCS '01]. Our technique has a unique feature that the lower bound is obtained by giving an explicit feasible solution to (the dual of) a certain linear programming problem. In fact, the problem itself was presented by the author over a decade ago [MFCS '05], and finding a good solution is an actual contribution of this work.