Theory Reading Group

Fall 2013 Reading Group Schedule

For this summer's reading group, we will follow Luca Trevisan's online course about Graph Partitioning and Expanders, which has both video lectures (on Luca's YouTube channel) and written lectures. A previous interation of this course (at Stanford) lists papers for possible course projects.

Date	Information
Wednesday August 28, 2013	Theory Reading Arora-Rao-Vazirani algorithm for sparsest cut Expander Flows, Geometric Embeddings and Graph Partitioning by Sanjeev Arora, Satish Rao, and Umesh Vazirani Geometry, Flows, and Graph-Partitioning Algorithms by Sanjeev Arora, Satish Rao, and Umesh Vazirani The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys Seeun William Umboh 2:00 pm, CS 4310
Wednesday August 21, 2013	Theory Reading Approximating the Expansion Profile and Almost Optimal Local Graph Clustering by Shayan Oveis Gharan, Luca Trevisan (Part 2) Kevin Kowalski 2:00 pm, CS 4310
Friday August 16, 2013	Theory Reading Approximating the Expansion Profile and Almost Optimal Local Graph Clustering by Shayan Oveis Gharan, Luca Trevisan (Part 1) Kevin Kowalski 2:00 pm, CS 4310
Thursday August 8, 2013	Theory Reading A Local Clustering Algorithm for Massive Graphs and its Application to Nearly-Linear Time Graph Partitioning by Daniel A. Spielman and Shang-Hua Teng (Part 2) Cong Han Lim and Local Graph Partitioning using PageRank Vectors by Reid Andersen, Fan Chung, and Kevin Lang (Part 2) Sarah Rich 2:00 pm, CS 4310
Wednesday July 31, 2013	Theory Reading Local Graph Partitioning using PageRank Vectors by Reid Andersen, Fan Chung, and Kevin Lang (Part 1) Sarah Rich 2:00 pm, CS 4310
Friday July 26, 2013	Theory Reading A Local Clustering Algorithm for Massive Graphs and its Application to Nearly-Linear Time Graph Partitioning by Daniel A. Spielman and Shang-Hua Teng (Part 1) Cong Han Lim 3:00 pm, CS 3310
Wednesday July 17, 2013	Theory Reading Semi-Direct Product in Groups and Zig-Zag Product in Graphs: Connections and Applications by Noga Alon, Alexander Lubotzky, and Avi Wigderson Sarah Rich 2:00 pm, CS 4310
Thursday June 27, 2013	Theory Reading Subexponential Algorithms for Unique Games and Related Problems (Part 2) Holger Dell 2:00 pm, CS 4310
Thursday June 20, 2013	Theory Reading Subexponential Algorithms for Unique Games and Related Problems (Part 1) On the Unique Games Conjecture by Subhash Khot (also invited talk at CCC 2010) Spectral Algorithms for Unique Games by Alexandra Kolla Subexponential Algorithms for Unique Games and Related Problems by Sanjeev Arora, Boaz Barak, and David Steurer Holger Dell 2:00 pm, CS 4310