Name
Abstract | ||
|---|---|---|
We show that any $n$-variate polynomial computable by a syntactically multilinear circuit of size $operatorname{poly}(n)$ can be computed by a depth-$4$ syntactically multilinear ($SigmaPiSigmaPi$) circuit of size at most $expleft({Oleft(sqrt{nlog n}right)}right)$. For degree $d = omega(n/log n)$, this improves upon the upper bound of $expleft({O(sqrt{d}log n)}right)$ obtained by Tavenas~cite{T15} for general circuits, and is known to be asymptotically optimal in the exponent when $d u003c n^{epsilon}$ for a small enough constant $epsilon$. Our upper bound matches the lower bound of $expleft({Omegaleft(sqrt{nlog n}right)}right)$ proved by Raz and Yehudayoff~cite{RY09}, and thus cannot be improved further in the exponent. Our results hold over all fields and also generalize to circuits of small individual degree. More generally, we show that an $n$-variate polynomial computable by a syntactically multilinear circuit of size $operatorname{poly}(n)$ can be computed by a syntactically multilinear circuit of product-depth $Delta$ of size at most $expleft(Oleft(Delta cdot (n/log n)^{1/Delta} cdot log nright)right)$. It follows from the lower bounds of Raz and Yehudayoff (CC 2009) that in general, for constant $Delta$, the exponent in this upper bound is tight and cannot be improved to $oleft(left(n/log nright)^{1/Delta}cdot log nright)$. |
Year | Venue | DocType |
|---|---|---|
2019 | international colloquium on automata, languages and programming | Journal |
Volume | Citations | PageRank |
26 | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mrinal Kumar 0001 | 1 | 64 | 9.94 |
| Rafael Mendes de Oliveira | 2 | 49 | 7.59 |
| Ramprasad Saptharishi | 3 | 184 | 13.72 |