Title: Fast Monte Carlo Algorithms for Massive Data Sets and
Approximating Max-Cut, Part II

Speaker: Michael W. Mahoney, Yale University

When/where: Thursday, February 19th, 4:15PM, 200 AKW

Abstract: We are interested in developing and analyzing fast Monte Carlo algorithms for performing 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 II of II; last month we provided an overview and this month we examine technical details. Although having attended the first part will help with the second part, it is NOT a prerequisite. This is joint work with Petros Drineas and Ravi Kannan.