Nimble Algorithms for Cloud Computing
Talkat Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013) · 2013-09-16..09-19
summary
Defines sublinear communication algorithms that use polynomial time/space but exchange far less than the data. Shows frequency moments across S servers by sampling by frequency^k, giving an estimator that uses about S^k/ε^2 words (so two-server third moment needs O(1/ε^2) samples). Uses limited‑independence random projections and subspace embeddings to compute low‑rank approximations with roughly S·k·d communication and small sketches; also builds coresets for k‑means under row partitions.
AI-written summary · about