Lower Bounds for Matrix Product
| dc.creator | Shpilka, Amir | |
| dc.date | 2002-01-02 | |
| dc.date.accessioned | 2026-07-07T03:18:02Z | |
| dc.date.available | 2026-07-07T03:18:02Z | |
| dc.description | We prove lower bounds on the number of product gates in bilinear and quadratic circuits that compute the product of two $n \cross n$ matrices over finite fields. In particular we obtain the following results: 1. We show that the number of product gates in any bilinear (or quadratic) circuit that computes the product of two $n \cross n$ matrices over $F_2$ is at least $3 n^2 - o(n^2)$. 2. We show that the number of product gates in any bilinear circuit that computes the product of two $n \cross n$ matrices over $F_p$ is at least $(2.5 + \frac{1.5}{p^3 -1})n^2 -o(n^2)$. These results improve the former results of Bshouty '89 and Blaser '99 who proved lower bounds of $2.5 n^2 - o(n^2)$. | |
| dc.description | Published in the proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS) 2001 | |
| dc.identifier | https://arxiv.org/abs/cs/0201001 | |
| dc.identifier | http://arxiv.org/abs/cs/0201001 | |
| dc.identifier | Published in the proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS) 2001 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/30955 | |
| dc.subject | Computational Complexity | |
| dc.subject | F.1.1; F.2.0 | |
| dc.title | Lower Bounds for Matrix Product | |
| dc.type | text |