Cloud computing suggests a model where communication between storage/computation devices is a bottleneck resource. An algorithm is nimble if it uses only sublinear (ideally polylogarithmic) communication and polynomial time and space. We expand on the model proposed by Cormode and Muthukrishnan and develop nimble algorithms for computing frequency moments, counting homomorphisms, low-rank approximation and k-means clustering.

This is joint work with Ravi Kannan and David Woodruff.