2026-07-23T16:50:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27069 2026-07-23T11:36:19Z ddc:004 open_access

Optimal Depth-Three Circuits for Inner Product Gurumukhani, Mohit Kleber, Daniel Paturi, Ramamohan Rosin, Christopher Talebanfard, Navid Depth 3 circuits Circuit lower bounds Inner product Analytic combinatorics We show that Inner Product in 2n variables, IP_n(x, y) = x₁y₁ ⊕ … ⊕ x_ny_n, can be computed by depth-3 bottom fan-in 2 circuits of size poly(n)⋅ (9/5)ⁿ, matching the lower bound of Göös, Guan, and Mosnoi (Inform. Comput.'24). Our construction is obtained via the following steps. 1) 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. 2) We instantiate the template for 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. 3) 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mohit Gurumukhani and Daniel Kleber and Ramamohan Paturi and Christopher Rosin and Navid Talebanfard 2026 Is Part Of LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2026.27 urn:nbn:de:0030-drops-270693 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.27 eng https://creativecommons.org/licenses/by/4.0/legalcode