ECCC-Report TR17-193https://eccc.weizmann.ac.il/report/2017/193Comments and Revisions published for TR17-193en-usSun, 31 Dec 2017 18:46:11 +0200
Paper TR17-193
| On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions |
Oded Goldreich,
Avishay Tal
https://eccc.weizmann.ac.il/report/2017/193We 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.
Sun, 31 Dec 2017 18:46:11 +0200https://eccc.weizmann.ac.il/report/2017/193