Applied Mathematics Colloquium

Monday October 14, 2013 4:15 PM

Nimble Algorithms for Cloud Computing

Speaker: Ravi Kannan, Microsoft Research, India
Location: Annenberg 105
A "nimble" algorithm works with data distributed among several polynomial time bounded processors, but with only poly-logarithmically bounded communication. We develop nimble algorithms for several problems of central interest in the context of large data. Among them are matrix computations like Singular Value Decomposition. For this, we will draw upon recent progress on subspace embeddings. We also tackle frequency moment problems. Many of these problems are provably impossible to solve in the only theoretically widely studied model of computing with large data, namely, the Streaming Model. We also develop nimble algorithms for counting the number of subgraphs in a large distributed graph as well as Clustering problems, where, we use results on Core Sets crucially. Probing the full extent of what is solvable in this model is of theoretical as well as practical interest.
Joint Work with Santosh Vempala and David Woodruff.
Series Applied Mathematics Colloquium Series

Contact: Sydney Garstang at x4555