Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR04-042 | 21st May 2004 00:00

Multilinear-$NC_1$ $\ne$ Multilinear-$NC_2$

RSS-Feed




TR04-042
Authors: Ran Raz
Publication: 25th May 2004 18:44
Downloads: 3579
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint