Multilinear- NC₁ ≠ Multilinear- NC₂
Ran Raz · 2004
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(x/sub 1/,..., x/sub n/), 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/sup 2/ n). (2) Any multilinear formula for f is of size n/sup /spl Omega/(log n)/. This gives a super-polynomial gap between multilinear circuit and formula size, and separates multilinear NC/sub 1/ circuits from multilinear NC/sub 2/ circuits.