Cameron Musco: Linear Sketching and Applications to Distributed Computation

I will give a basic introduction to linear sketching, reviewing important tools that include the Johnson-Lindenstrauss lemma and Heavy-Hitter (sparse recovery) sketches. I will show how these techniques can be applied to reduce communication in distributed settings. I will talk about our recent work on k-means clustering and spectral graph sparsification, and discuss potential open questions about how sketching can be further applied to distributed computing.