ECCC-Report TR13-043https://eccc.weizmann.ac.il/report/2013/043Comments and Revisions published for TR13-043en-usTue, 25 Feb 2014 09:57:22 +0200
Revision 1
| On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions |
Oded Goldreich,
Avi Wigderson
https://eccc.weizmann.ac.il/report/2013/043#revision1We 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))$.
Tue, 25 Feb 2014 09:57:22 +0200https://eccc.weizmann.ac.il/report/2013/043#revision1
Paper TR13-043
| On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions |
Oded Goldreich,
Avi Wigderson
https://eccc.weizmann.ac.il/report/2013/043We 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))$.
Mon, 25 Mar 2013 11:22:47 +0200https://eccc.weizmann.ac.il/report/2013/043