Title: "Fast Monte Carlo Algorithms for Massive Data Sets and for
Approximating Max-Cut"

Speaker: Michael W. Mahoney, Gibbs Instructor in Applied Mathematics,
Yale University

When/where: Tuesday, January 13th, 4:15PM, 200 AKW

Abstract:We are interested in developing and analyzing fast Monte Carlo algorithms forperforming useful computations on large matrices. Examples of such computations include matrix multiplication, the computation of the Singular Value Decomposition of a matrix, the computation of compressed approximate
decompositions of a matrix, and testing the feasibility or infeasibility of a linear program. We present a Pass-Efficient model of data streaming computation in which our algorithms may naturally be formulated and present algorithms that are efficient within this model for each of the four types of matrix operations mentioned previously. We also discuss applications of these methods to the analysis of massive data sets and outline an improved algorithm for the Max-Cut problem that uses these methods. This talk is part I of II; technical details will be deferred to an informal seminar in the near future. This is joint work with Petros Drineas and Ravi Kannan.