Abstract
An arithmetic circuit or formula is multilinear if the polynomial computed at each of its wires is multilinear. We give an explicit example for a polynomial f(x1, ..., xn), with coefficients in {0, 1}, such that over any field: 1. f can be computed by a polynomial-size multilinear circuit of depth O(log² n). 2. 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₁ circuits from multilinear NC₂ circuits.