Lower bounds for matrix product
Author:
- 1 January 2001
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15525244,p. 358-367
Abstract
We prove lower bounds on the number of product gates in bilinear and quadratic circuits that compute the product of two n /spl times/ 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 /spl times/ n matrices over GF(2) is at least 3n/sup 2/ o(n/sup 2/). 2. We show that the number of product gates in any bilinear circuit that computes the product of two n /spl times/ n matrices over GF(p) is at least (2.5 + 1.5/p/sup 3/-1)n/sup 2/ - o(n/sup 2/). These results improve the former results of N.H. Bshouty (1997) and M. Blaser (1999) who proved lower bounds of 2.5n/sup 2/ o(n/sup 2/).Keywords
This publication has 10 references indexed in Scilit:
- Lower bounds for matrix product, in bounded depth circuits with arbitrary gates2001
- Lower bounds for the bilinear complexity of associative algebrascomputational complexity, 2000
- Algebraic Complexity Theory1997
- Introduction to Coding Theory1992
- Matrix multiplication via arithmetic progressionsJournal of Symbolic Computation, 1990
- A Lower Bound for Matrix MultiplicationSIAM Journal on Computing, 1989
- Algebraic Complexity TheoryAnnual Review of Computer Science, 1988
- Fast Probabilistic Algorithms for Verification of Polynomial IdentitiesJournal of the ACM, 1980
- Probabilistic algorithms for sparse polynomials1979
- Gaussian elimination is not optimalNumerische Mathematik, 1969