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 extend of what is solvable in this model is of theoretical as well as practical interest.

Joint Work with Santosh Vempala and David Woodruff