Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR17-193 | 31st December 2017 18:45

On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions

RSS-Feed




TR17-193
Authors: Oded Goldreich, Avishay Tal
Publication: 31st December 2017 18:46
Downloads: 887
Keywords: 


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.



ISSN 1433-8092 | Imprint