Algorithms, Geometry and Learning

Summer 2017, Stanford University

Here you can find detailed references and reading material related to the topics covered.

Low Strech Spanning Trees

Lower-Stretch Spanning Trees, Michael Elkin, Yuval Emek, Daniel A. Spielman, Shang-Hua Teng, SICOMP 2008.
Nearly tight low stretch spanning trees, I. Abraham, Y. Bartal, O. Neiman, FOCS 2008.
Using petal-decompositions to build a low stretch spanning tree, I. Abraham, O. Neiman, STOC 2012.
Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion, I. Abraham, Y. Bartal, O. Neiman, SODA 2007.

Spectral Sparsifiers and Effective Resistances.

Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP, N. Anari, S. Oveis Gharan, FOCS 2015.
Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time, Yin Tat Lee, He Sun, FOCS 2015.
An SDP-Based Algorithm for Linear-Sized Spectral Sparsification, Yin Tat Lee, He Sun, STOC 2017.
Density Independent Algorithms for Sparsifying k-Step Random Walks, G. Jindal, P. Kolev, Richard Peng, S. Sawlani, 2017.
Fast Generation of Random Spanning Trees and the Effective Resistance Metric, A. Madry et al., SODA 2015.
Sampling Random Spanning Trees Faster than Matrix Multiplication, D. Durfee et al., 2016.

Decomposing a Graph into Expanders

Almost Optimal Local Graph Clustering Using Evolving Sets, R. Andersen, S. Oveis Gharan, Y. Peres, L. Trevisan, JACM 2016.
Decomposing a graph into expanding subgraphs,G. Moshkovitz, A. Shapira, SODA 2015.
Partitioning into expanders, Shayan Oveis Gharan, Luca Trevisan, SODA 2014.
Finding and using expanders in locally sparse graphs, M. Krivevelich, 2017.
Approximation Algorithms for Finding Maximum Induced Expanders, Shayan Oveis Gharan, Alireza Rezaei
Multi-way dual Cheeger constants and spectral bounds of graphs, S. Liu, Advances in Mathematics 2015.

Spectral Embedding

Sharp Bounds on Random Walk Eigenvalues via Spectral Embedding, Russell Lyons, Shayan Oveis Gharan, 2017.
How to round subspaces: a new spectral clustering algorithm, Ali-Kemal Sinop, SODA 2016.
Multiway spectral partitioning and higher-order Cheeger inequalities, J.R. Lee, S. Oveis Gharan, L. Trevisan, STOC 2012.
A Note on Spectral Clustering, P. Kolev, K. Mehlhorn, ESA 2016.