45th Annual IEEE Symposium on Foundations of Computer Science
Download PDF

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.
Like what you’re reading?
Already a member?Sign In
Member Price
$11
Non-Member Price
$21
Add to CartSign In
Get this article FREE with a new membership!

Related Articles