Separation of Multilinear Circuit and Formula Size

Raz, Ran

doi:10.4086/toc.2006.v002a006

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

Download article from ToC site:
[PDF (169K)] [PS (294K)] [Source ZIP]

Misc.:
[About the Author] [HTML Bibliography] [BibTeX]

Keywords: algebraic complexity, arithmetic circuits, log-depth, multilinear polynomials, lower bounds, separation of complexity classes

Categories: complexity theory, lower bounds, circuits, arithmetic circuits, formulas, arithmetic formulas, complexity classes, separation of complexity classes, polynomials - multivariate

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(x_1,\dots,x_n)$ with coefficients in $\{0,1\}$ such that over any field:

$f$ can be computed by a polynomial-size multilinear circuit of depth $O(\log^2 n)$ .
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.

DOI: 10.4086/toc.2006.v002a006

Licensed under a Creative Commons License