Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with depth-three Boolean circuits:
TR13-043 | 25th March 2013
Oded Goldreich, Avi Wigderson

On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions

Revisions: 1

We propose that multi-linear functions of relatively low degree
over GF(2) may be good candidates for obtaining exponential
lower bounds on the size of constant-depth Boolean circuits
(computing explicit functions).
Specifically, we propose to move gradually from linear functions
to multilinear ones, and conjecture that, for any $t\geq2$,
more >>>

TR19-171 | 27th November 2019
Oded Goldreich

Improved bounds on the AN-complexity of multilinear functions

Revisions: 3

We consider arithmetic circuits with arbitrary large (multi-linear) gates for computing multi-linear functions. An adequate complexity measure for such circuits is the maximum between the arity of the gates and their number.
This model and the corresponding complexity measure were introduced by Goldreich and Wigderson (ECCC, TR13-043, 2013), ... more >>>

ISSN 1433-8092 | Imprint