## On Constant-Depth Canonical Boolean Circuits
for Computing Multilinear Functions

#### Webpage for a paper by Oded Goldreich and Avishay Tal

#### Abstract

We consider new complexity measures for the model
of multilinear circuits with general multilinear gates
introduced by Goldreich and Wigderson (ECCC, 2013).
These complexity measures are related to the size
of canonical constant-depth Boolean circuits,
which extend the definition of canonical depth-three Boolean circuits.
We obtain matching lower and upper bound on the size of canonical
constant-depth Boolean circuits for almost all multilinear functions,
and non-trivial lower bounds on the size of such circuits
for some explicit multilinear functions.

#### Material available on-line

- First version posted:
Dec 2017.
- Revisions: none yet.

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