Optimal Depth-Three Circuits for Inner Product
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911441974460416 |
|---|---|
| author | Gurumukhani, Mohit Kleber, Daniel Paturi, Ramamohan Rosin, Christopher Talebanfard, Navid |
| author_facet | Gurumukhani, Mohit Kleber, Daniel Paturi, Ramamohan Rosin, Christopher Talebanfard, Navid |
| contents | 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 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 $f^{-1}(1)$ into orbits of its automorphism group. 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$.
- We instantiate the template for $\mathbf{IP}_n$ and $k = 2$. Guided by the intuition (which we call modularity principle) that optimal 2-CNFs can be constructed by taking the conjunction of variable-disjoint copies of smaller $2$-CNFs, we use computer search to identify a small set of building block 2-CNFs over at most 4 variables.
- We again use computer search to discover appropriate combinations (disjoint conjunctions) of building blocks to arrive at optimal 2-CNFs and analyze them using techniques from analytic combinatorics.
We believe that the approach outlined in this paper can be applied to a wide range of functions to determine their depth-3 complexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_04446 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Optimal Depth-Three Circuits for Inner Product Gurumukhani, Mohit Kleber, Daniel Paturi, Ramamohan Rosin, Christopher Talebanfard, Navid Computational Complexity 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 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 $f^{-1}(1)$ into orbits of its automorphism group. 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$. - We instantiate the template for $\mathbf{IP}_n$ and $k = 2$. Guided by the intuition (which we call modularity principle) that optimal 2-CNFs can be constructed by taking the conjunction of variable-disjoint copies of smaller $2$-CNFs, we use computer search to identify a small set of building block 2-CNFs over at most 4 variables. - We again use computer search to discover appropriate combinations (disjoint conjunctions) of building blocks to arrive at optimal 2-CNFs and analyze them using techniques from analytic combinatorics. We believe that the approach outlined in this paper can be applied to a wide range of functions to determine their depth-3 complexity. |
| title | Optimal Depth-Three Circuits for Inner Product |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2601.04446 |