Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR00-029 | 18th June 2000 00:00

Lower Bounds for Matrix Product, in Bounded Depth Circuits with Arbitrary Gates Revision of: TR00-029

RSS-Feed




Revision #1
Authors: Ran Raz, Amir Shpilka
Accepted on: 18th June 2000 00:00
Downloads: 2115
Keywords: 


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.


Paper:

TR00-029 | 30th April 2000 00:00

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





TR00-029
Authors: Ran Raz, Amir Shpilka
Publication: 28th May 2000 08:08
Downloads: 3967
Keywords: 


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.



ISSN 1433-8092 | Imprint