SPEAKER: Ryan Williams

TIME: Wednesday 12-1pm, January 17, 2007

PLACE: NSH 1507

TITLE: Matrix-Vector Multiplication in Subquadratic Time (Some Preprocessing
Required)

ABSTRACT:
We show that any n by n matrix A over any finite semiring can be preprocessed 
in O(n^{2+eps}) time, such that all subsequent vector multiplications with A 
can be performed in O(n^2/(eps log n)^2) time, for all eps > 0. The approach 
is combinatorial and can be implemented on a pointer machine or a (log n)-
word RAM. Some applications are described.

A bit shorter version of this talk was presented last week, at SODA in New 
Orleans.