Answers are grounded in this paper and cite their sources.
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.
No takes yet. Share an insight, caveat, or question.
Göös et al. (2023) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: