Optimal Depth-Three Circuits for Inner Product

Mohit Gurumukhani, Daniel Kleber, Ramamohan Paturi, Christopher Rosin, Navid Talebanfard · 2026

Read Optimal Depth-Three Circuits for Inner Product by Mohit Gurumukhani, Daniel Kleber, Ramamohan Paturi, Christopher Rosin, Navid Talebanfard (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-04446.txt.

Description

Mohit Gurumukhani and four co-authors settle the exact cost of computing the inner product with shallow circuits, in a 2026 arXiv paper. The inner product of two strings — the parity of their overlapping ones — is a benchmark function in circuit complexity. for depth-three circuits whose bottom gates read just two inputs, a lower bound on size was proven recently. The question was whether any construction could actually meet it.

Theirs does. The team first builds a general template: split the function's accepting inputs by its symmetries, then cover each family with the greediest formula that accepts nothing outside the function. Guided by a modularity principle, they let computer search find small building-block formulas and the disjoint combinations that assemble them, then prove the count with analytic combinatorics. The resulting circuit size matches the lower bound exactly, and the authors believe the template transfers to other functions.

Catalog record

CREATORMohit Gurumukhani, Daniel Kleber, Ramamohan Paturi, Christopher Rosin, Navid Talebanfard
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE86 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-04446

Browse the full library · About the Tower of Babel