45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04)
Multilinear- NC₁ ≠ Multilinear- NC₂
Rome, Italy
October 17-October 19
ISBN: 0-7695-2228-9
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.