Summary: In this paper, we study the size of depth-two threshold circuits computing the inner product mod 2 function \(\mathsf{IP2}_n(x_1,\dots,x_n,y_1,\dots,y_n) := \sum_i x_i y_i \pmod 2\). First, we reveal that \(\mathsf{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 \(\mathsf{THR}\circ\mathsf{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 gate are polynomially bounded (denoted by \(\mathsf{MAJ}\circ\mathsf{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 \(\mathsf{THR}\circ\mathsf{SYM}\) circuit). We show that any such circuit computing \(\mathsf{IP2}_n\) has size \(\varOmega ((1.5-\varepsilon)^n)\) for every constant \(\varepsilon>0\). This improves the previous bound of \(\varOmega(\sqrt{2}^n/n)\) based on the sign-rank method due to J. Forster et al. [Lect. Notes Comput. Sci. 2245, 171–182 (2001; Zbl 1052.68051)]. 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 and A. Maruoka over a decade ago [Lect. Notes Comput. Sci. 3618, 107–118 (2005; Zbl 1156.68389)], and finding a good solution is an actual contribution of this work.
For the entire collection see [Zbl 1435.68034].