On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions

Webpage for a paper by Oded Goldreich and Avishay Tal


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

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