Lower Bounds for Matrix Product

Original · EN

We prove lower bounds on the number of product gates in bilinear and quadratic circuits that compute the product of two n 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 n matrices over F₂ is at least 3 n² - o(n²). 2. We show that the number of product gates in any bilinear circuit that computes the product of two n n matrices over Fₚ is at least (2.5 + 1.5/p³ -1)n² -o(n²). These results improve the former results of Bshouty '89 and Blaser '99 who proved lower bounds of 2.5 n² - o(n²).