Volume 2 (2006)
Article 6 pp. 121-135
Separation of Multilinear Circuit and Formula Size
by Ran Raz
Received: September 30, 2005
Revised: March 4, 2006
Published: May 2, 2006
DOI: 10.4086/toc.2006.v002a006
Keywords: arithmetic circuits, log-depth, multilinear polynomials, lower bounds, separation of complexity classes
ACM Classification: F.2.2, F.1.3, F.1.2, G.2.0
AMS Classification: 68Q15, 68Q17, 68Q25, 94C05
Abstract:
[Plain Text Version]
An arithmetic circuit or formula is multilinear if the polynomial computed
at each of its wires is multilinear. We give an explicit polynomial
f(x1,...,xn) with coefficients in
{0,1} such that over any field:
- f can be computed by a polynomial-size multilinear circuit
of depth O(log2n).
- Any multilinear formula for f is of size
nΩ(log n).
This gives a super-polynomial gap between multilinear circuit
and formula size, and separates multilinear
NC1 circuits
from multilinear
NC2 circuits.
