Theory of Computing
-------------------
Title     : Separation of Multilinear Circuit and Formula Size
Authors   : Ran Raz
Volume    : 2
Number    : 6
Pages     : 121-135
URL       : http://www.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.