Authors
Oded Goldreich, Avishay Tal
Publication date
2020
Journal
Computational Complexity and Property Testing: On the Interplay Between Randomness and Computation
Pages
306-325
Publisher
Springer International Publishing
Description
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.
Total citations
20202021202220232024111
Scholar articles
O Goldreich, A Tal - Computational Complexity and Property Testing: On …, 2020