Optimal Depth-Three Circuits for Inner Product

Optimal depth 3 circuits for IP - arXiv abstract We show that Inner Product in $2n$ variables, $\mathbf{IP}_n(x, y) = x_1y_1 \oplus \ldots \oplus x_ny_n$, can be computed by depth-3 bottom fan-in 2 circuits of size $\mathsf{poly}(n)\cdot (9/5)^n$, matching the lower bound of Göös, Guan, and Mosnoi (Inform. Comput.'24). Our construction is given via the following steps. - We provide a general template for constructing optimal depth-3 circuits with bottom fan-in $k$ for an arbitrary function $f$. We do this in two steps. First, we partition the accepting inputs to $f$ into several carefully defined orbits. Second, for each orbit, we construct one $k$-CNF that (a) accepts the largest number of inputs from that orbit and (b) rejects all inputs rejected by $f$. This partitioning of inputs into orbits is based on the symmetries of $f$. - We instantiate the template for $\mathbf{IP}_n$ and $k = 2$. Guided by a modularity principle that these optimal 2-CNFs may be constructed by composing variable-disjoint copies of small formulas, we use computer search to identify a small set of 2-CNFs each on at most 4 variables which we call building blocks. - We then use analytic combinatorial techniques to determine optimal ways to combine these building blocks and construct these optimal 2-CNFs. We believe that the above steps can be applied to a wide range of functions to determine their depth-3 complexity.