Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > TIBERIU MOSNOI:
All reports by Author Tiberiu Mosnoi:

TR23-106 | 17th July 2023
Mika Göös, Ziyi Guan, Tiberiu Mosnoi

Depth-3 Circuits for Inner Product

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




ISSN 1433-8092 | Imprint