Oded Goldreich, Avi Wigderson

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 >>>

Oded Goldreich

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 >>>