ColloquiaTalk by Amir Shpilka - Monday, March 3, 2003

[Margery Ishmael]

----------------------------------------------------------------------------

DEPARTMENT OF COMPUTER SCIENCE - TALK

Monday, March 3rd, 2003 at 2:30 pm, Ryerson 251

----------------------------------------------------------------------------

Speaker: AMIR SHPILKA, Harvard University
http://www.deas.harvard.edu/~amirs

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).

*The talk will be followed by refreshments in Ryerson 255*

Hosts: Laci Babai & Eric Vigoda


=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Margery Ishmael
Secretary to the Chairman, Department of Computer Science
The University of Chicago
1100 E. 58th Street, Chicago, IL. 60637-1581
tel. 773.834.8977 fax. 773.702.8487
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-