Sunday, May 21, 14:15-15:15
at 14:00
Schreiber Building, Room 309
In particular, we obtain the following results:
1) We show that the number of edges in any constant depth arithmetic
circuit for {\bf matrix product} (over any field) is super-linear in
$m^2$
(where $m \times m$ is the size of each matrix).
That is, the lower bound is super-linear in the number of input variables.
Moreover, if the circuit is bilinear the result applies also for the
case
where the circuit gets for free any product of two linear functions.
2) We show that the number of edges in any constant depth arithmetic
circuit for the trace of the product of 3 matrices (over fields with
characteristic 0) is super-linear in $m^2$.
(Note that the trace is a {\bf single-output} function).
3) We give explicit examples for $n$ Boolean functions $f_1,...,f_n$,
such that any constant depth {\bf Boolean circuit with arbitrary gates}
for $f_1,...,f_n$ has a super-linear number of edges.
In particular, this gives explicit lower bounds for constant depth
threshold circuits (the class $TC_0$) and for constant depth neural
networks.
The lower bound is proved also for {\bf circuits with arbitrary gates
over any finite field}.
The bound applies for matrix product over finite fields
as well as for several other explicit functions.
Joint work with Amir Shpilka
For colloquium schedule, see http://www.math.tau.ac.il/~zwick/colloq.html