Optimal Depth-Three Circuits for Inner Product
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 obtained via the following steps. - We...