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 [Formula: see text] (mod 2). First, we reveal that [Formula: see text] can be computed by a depth-two threshold circuit of size significantly smaller than a folklore construction of size [Formula: see text]. Namely, we give a construction of such a circuit (denoted by [Formula: see text] circuit) of size [Formula: see text]. We also give an upper bound of [Formula: see text] for the case that the weights of the top threshold gate are polynomially bounded (denoted by [Formula: see text] 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 [Formula: see text] circuit). We show that any such circuit computing [Formula: see text] has size [Formula: see text] for every constant [Formula: see text]. This improves the previous bound of [Formula: see text] 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.