__
TR04-042 | 21st May 2004 00:00
__

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

TR04-042
Authors:

Ran Raz
Publication: 25th May 2004 18:44

Downloads: 3286

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.