Applied Mathematics Colloquium
Annenberg 105
Nimble Algorithms for Cloud Computing
Ravi Kannan,
Principal Researcher,
Microsoft Research, India,
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 Woodru ff.
For more information, please contact Sydney Garstang by phone at x4555 or by email at [email protected].
Event Series
Applied Mathematics Colloquium Series