16
Jan
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.
