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.