ECCC-Report TR00-029https://eccc.weizmann.ac.il/report/2000/029Comments and Revisions published for TR00-029en-usSun, 18 Jun 2000 00:00:00 +0300
Revision 1
| Lower Bounds for Matrix Product, in Bounded Depth Circuits with Arbitrary Gates Revision of: TR00-029 |
Ran Raz,
Amir Shpilka
https://eccc.weizmann.ac.il/report/2000/029#revision1We 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.
Sun, 18 Jun 2000 00:00:00 +0300https://eccc.weizmann.ac.il/report/2000/029#revision1
Paper TR00-029
| Lower Bounds for Matrix Product, in Bounded Depth Circuits with Arbitrary Gates |
Ran Raz,
Amir Shpilka
https://eccc.weizmann.ac.il/report/2000/029We 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.
Sun, 28 May 2000 08:08:15 +0300https://eccc.weizmann.ac.il/report/2000/029