Theory of Computing
-------------------
Title : Separation of Multilinear Circuit and Formula Size
Authors : Ran Raz
Volume : 2
Number : 6
Pages : 121-135
URL : https://theoryofcomputing.org/articles/v002a006
Abstract
--------
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,...,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 super-polynomial gap between multilinear circuit
and formula size, and separates multilinear NC_1 circuits
from multilinear NC_2 circuits.