On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions.
Oded Goldreich, Avi Wigderson · 2013
We propose that multi-linear functions of relatively low degree over GF(2) may be good candidates for obtaining exponential1 lower bounds on the size of constant-depth Boolean cir-cuits (computing explicit functions). Specifically, we propose to move gradually from linear functions to multilinear ones, and conjecture that, for any t ≥ 2, some explicit t-linear functions F: ({0, 1}n)t → {0, 1} require depth-three circuits of size exp(Ω(tnt/(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