Under the auspices of the Computational Complexity Foundation (CCF)

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