ColloquiaReminder of today's theory talk

[Eric Vigoda]

Amir Shpilka
2:30 PM in Ryerson 251

Title: Lower Bounds for Matrix Multiplication

Abstract:

We prove lower bounds on the number of product gates in bilinear and
quadratic circuits that compute the product of two nxn matrices over
finite fields. In particular we obtain the following results:

1. We show that the number of product gates in any bilinear circuit that
computes the product of two nxn matrices over GF(2) is at least 3n^2 -
o(n^2)$.

2. We show that the number of product gates in any bilinear circuit that
computes the product of two nxn matrices over GF(q) is at least (2.5 +
{1.5}/{q^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.5n^2 - o(n^2).