TR23-106 Authors: Mika Göös, Ziyi Guan, Tiberiu Mosnoi

Publication: 18th July 2023 01:12

Downloads: 542

Keywords:

What is the $\Sigma_3^2$-circuit complexity (depth 3, bottom-fanin 2) of the $2n$-bit inner product function? The complexity is known to be exponential $2^{\alpha_n n}$ for some $\alpha_n=\Omega(1)$. We show that the limiting constant $\alpha=\limsup \alpha_n$ satisfies

\[

0.847... ~\leq~ \alpha ~\leq~ 0.965...\ .

\]

Determining $\alpha$ 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 $\alpha\in[0.5,1]$. To obtain our improved bounds, we analyse a covering LP that captures the $\Sigma_3^2$-complexity up to polynomial factors. In particular, our lower bound is proved by constructing a feasible solution to the dual LP.