All reports by Author Tiberiu Mosnoi:

__
TR23-106
| 17th July 2023
__

Mika Göös, Ziyi Guan, Tiberiu Mosnoi#### Depth-3 Circuits for Inner Product

Mika Göös, Ziyi Guan, Tiberiu Mosnoi

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 ...
more >>>