2026-08-01T15:10:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18585 2024-03-06T11:02:11Z ddc:004 open_access

Depth-3 Circuits for Inner Product Göös, Mika Guan, Ziyi Mosnoi, Tiberiu Circuit complexity inner product What is the Σ₃²-circuit complexity (depth 3, bottom-fanin 2) of the 2n-bit inner product function? The complexity is known to be exponential 2^{α_n n} for some α_n = Ω(1). We show that the limiting constant α := lim sup α_n satisfies 0.847... ≤ α ≤ 0.965... . Determining α is one of the seemingly-simplest open problems about depth-3 circuits. The question was recently raised by Golovnev, Kulikov, and Williams (ITCS 2021) and Frankl, Gryaznov, and Talebanfard (ITCS 2022), who observed that α ∈ [0.5,1]. To obtain our improved bounds, we analyse a covering LP that captures the Σ₃²-complexity up to polynomial factors. In particular, our lower bound is proved by constructing a feasible solution to the dual LP. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mika Göös and Ziyi Guan and Tiberiu Mosnoi 2023 Is Part Of LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2023.51 urn:nbn:de:0030-drops-185856 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.51 eng https://creativecommons.org/licenses/by/4.0/legalcode