-----------
Tel-Aviv University - Computer Science Colloquium

Sunday, May 21, 14:15-15:15
COFFEE at 14:00

Schreiber Building, Room 309
-----------

Lower Bounds for Matrix Product, in Bounded Depth Circuits with Arbitrary Gates

Ran Raz

Weizmann Institute

Abstract:

We prove super-linear lower bounds for the number of edges in constant
depth circuits with $n$ inputs and up to $n$ outputs. Our lower bounds
are proved for all types of constant depth circuits, e.g., constant
depth arithmetic circuits, constant depth threshold circuits and constant
depth Boolean circuits with arbitrary gates.
The bounds apply for several explicit functions, and, most importantly, for
matrix product.

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