Volume 2 (2006) Article 6 pp. 121-135
Separation of Multilinear Circuit and Formula Size
by Ran Raz
Revised: March 4, 2006
Published: May 2, 2006
An arithmetic circuit or formula is multilinear if the polynomial computed at each of its wires is multilinear. We give an explicit polynomial $f(x_1,\dots,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 superpolynomial gap between multilinear circuit and formula size, and separates multilinear $NC_1$ circuits from multilinear $NC_2$ circuits.