Multilinearity Can Be Exponentially Restrictive (Preliminary Version)
Rimli Sengupta, H. Venkateswaran · SMARTech Repository (Georgia Institute of Technology) · 1994
We define a Boolean circuit to be multilinear if the formal polynomial associated with it is multilinear as well. We consider the problem of computing the connectivity function using circuits that are monotone and multilinear. Our main result is that monotone multilinear circuits for this function require exponential size. Since connectivity can be computed by monotone Boolean circuits within size O(n³), our lower bound establishes that at least in the context of monotone computation, multilinearity can be exponentially restrictive. As an application of our lower bound, we show that connectivity is not in mNL, thereby improving a recent result by Yao that connectivity is not in mNC¹.