Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > ARITMETIC CIRCUIT:
Reports tagged with Aritmetic Circuit:
TR19-019 | 19th February 2019
Mrinal Kumar, Rafael Mendes de Oliveira, Ramprasad Saptharishi

Towards Optimal Depth Reductions for Syntactically Multilinear Circuits

We show that any $n$-variate polynomial computable by a syntactically multilinear circuit of size $\mathop{poly}(n)$ can be computed by a depth-$4$ syntactically multilinear ($\Sigma\Pi\Sigma\Pi$) circuit of size at most $\exp\left({O\left(\sqrt{n\log n}\right)}\right)$. For degree $d = \omega(n/\log n)$, this improves upon the upper bound of $\exp\left({O(\sqrt{d}\log n)}\right)$ obtained by Tavenas (MFCS ... more >>>




ISSN 1433-8092 | Imprint