Computer Science – Computational Complexity
Scientific paper
2002-01-02
Published in the proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS) 2001
Computer Science
Computational Complexity
Published in the proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS) 2001
Scientific paper
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)$.
No associations
LandOfFree
Lower Bounds for Matrix Product does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Lower Bounds for Matrix Product, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lower Bounds for Matrix Product will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-564912