ECCC-Report TR04-042https://eccc.weizmann.ac.il/report/2004/042Comments and Revisions published for TR04-042en-usTue, 25 May 2004 18:44:56 +0300
Paper TR04-042
| Multilinear-$NC_1$ $\ne$ Multilinear-$NC_2$ |
Ran Raz
https://eccc.weizmann.ac.il/report/2004/042An arithmetic circuit or formula is multilinear if the polynomial
computed at each of its wires is multilinear.
We give an explicit example for a polynomial $f(x_1,...,x_n)$,
with coefficients in $\{0,1\}$, such that over any field:
1) $f$ can be computed by a polynomial-size multilinear circuit
of depth $O(\log^2 n)$.
2) Any multilinear formula for $f$ is of size $n^{\Omega(\log n)}$.
This gives a super-polynomial gap between multilinear circuit
and formula size, and separates multilinear $NC_1$ circuits
from multilinear $NC_2$ circuits.
Tue, 25 May 2004 18:44:56 +0300https://eccc.weizmann.ac.il/report/2004/042