On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions

Webpage for a paper by Oded Goldreich and Avi Wigderson


Abstract

We propose that multi-linear functions of relatively low degree over GF(2) may be good candidates for obtaining exponential lower bounds on the size of constant-depth Boolean circuits (computing explicit functions). Specifically, we propose to move gradually from linear functions to multilinear ones, and conjecture that, for any $t\geq2$, some explicit $t$-linear functions $F:(\{0,1\}^n)^t\to\{0,1\}$ require depth-three circuits of size $\exp(\Omega(tn^{t/(t+1)}))$.

Towards studying this conjecture, we suggest to study two frameworks for the design of depth-three Boolean circuits computing multilinear functions, yielding restricted models for which lower bounds may be easier to prove. Both correspond to constructing a circuit by expressing the target polynomial as a composition of simpler polynomials. The first framework corresponds to a direct composition, whereas the second (and stronger) framework corresponds to nested composition and yields depth-three Boolean circuits via a "guess-and-verify" paradigm in the style of Valiant. The corresponding restricted models of circuits are called D-canonical and ND-canonical, respectively.

Our main results are (1) a generic upper bound on the size of depth-three D-canonical circuits for computing any $t$-linear function, and (2) a lower bound on the size of any depth-three ND-canonical circuits for computing some (in fact, almost all) $t$-linear functions. These bounds match the foregoing conjecture (i.e., they have the form of $\exp(tn^{t/(t+1)})$). Another important result is separating the two models: We prove that ND-canonical circuits can be super-polynomially smaller than their D-canonical counterparts. We also reduce proving lower bounds for the ND-model to Valiant's matrix rigidity problem (for parameters that were not the focus of previous works).

The study of the foregoing (Boolean) models calls for an understanding of new types of arithmetic circuits, which we define in this paper and may be of independent interest. These circuits compute multilinear polynomials by using arbitrary multilinear gates of some limited arity. It turns out that a GF(2)-polynomial is computable by such circuits with at most $s$ gates of arity at most $s$ if and only if it can be computed by ND-canonical circuits of size $\exp(s)$. A similar characterization holds for D-canonical circuits if we further restrict the arithmetic circuits to have depth two. We note that the new arithmetic model makes sense over any field, and indeed all our results carry through to all fields. Moreover, it raises natural arithmetic complexity problems which are independent of our original motivation.

NOTE: Throughout this paper, when we say that a function $f$ is exponential, we mean that $f(n)=\exp(\Theta(n))$.

Material available on-line

Alternative summary

This paper introduces and initiates a study of a new model of arithmetic circuits coupled with new complexity measures. The new model consists of multilinear circuits with arbitrary multilinear gates, rather than the standard multilinear circuits that use only addition and multiplication gates. In light of this generalization, the arity of gates of crucial importance and is indeed one of our complexity measures. Our second complexity measure is the number of gates the circuit, which (in our context) is significantly different from the number of wires in the circuit (which is typically used as a measure of size). Our main complexity measure, denoted $C$, is the maximum of these two measures (i.e., the maximum between the arity of the gates and the number of gates in the circuit). We also consider the depth of such circuits, focusing on depth-two and unbounded depth.

Our initial motivation for the study of this arithmetic model is the fact that the two main variants (i.e., depth-two and unbounded depth) yield natural classes of depth-three Boolean circuits for computing multi-linear functions. The resulting circuits have size that is exponential in the new complexity measure. Hence, lower bounds on the new complexity measure yield lower bounds on a restricted class of depth-three Boolean circuits (for computing multi-linear functions). Such lower bounds are a sanity check for our conjecture that multi-linear functions of relatively low degree over GF(2) are good candidates for obtaining exponential lower bounds on the size of constant-depth Boolean circuits (computing explicit functions). Specifically, we propose to move gradually from linear functions to multilinear ones, and conjecture that, for any $t\geq2$, some explicit $t$-linear functions $F:(\bitset^n)^t\to\bitset$ require depth-three circuits of size $\exp(\Omega(tn^{t/(t+1)}))$.

Letting $C_2$ denote the complexity measure $C$, when minimized over all depth-two circuits of the above type, our main results are as follows.

The main open problem posed in this paper is proving a result analogous to~(2) for an explicit function $F$. For starters, we seek lower bound of $\Omega((tn)^{0.51})$ for an explicit $t$-linear function $F$, preferably for constant $t$. We outline an approach that reduces this challenge (for $t=3$) to a question regarding matrix rigidity.

Material added to the revision (of Feb'14)

In Section 4.3, we introduce a relaxed notion rigidity, which we call structured rigidity. We observe that structured rigidity may replace standard rigidity in our lower bound reductions, whereas the two notions can be strictly separated. In Section 5.1, we study arithmetic circuits that compute functions without relying on cancellations. We show that such circuits are weaker than the general arithmetic circuits considered in the bulk of the paper. (The original Section 5 was moved to Section 5.2.)


Back to either Oded Goldreich's homepage or general list of papers.