Algorithmic Spectral Graph Theory Boot Camp

Aug. 26 – Aug. 29, 2014

The Boot Camp is intended to acquaint program participants with the key themes of the program. Each speaker will give a sequence of three lectures on the topics below.

Click on the titles of individual talks for abstract, slides and archived video.

All events take place in the Calvin Lab Auditorium.

Tuesday, August 26th, 2014
9:30 am – 9:50 am		Coffee and Check-In
9:50 am – 10:00 am		Opening Remarks
10:00 am – 11:00 am		Spectral Graph Theory I: Introduction to Spectral Graph Theory Luca Trevisan, UC Berkeley
11:00 am – 11:30 am		Break
11:30 am – 12:30 pm		Graph Sparsification I: Sparsification via Effective Resistances Nikhil Srivastava, Microsoft Research India
12:30 pm – 2:00 pm		Lunch
2:00 pm – 3:00 pm		Spectral Graph Theory II: Expanders and Eigenvalues Luca Trevisan, UC Berkeley
3:00 pm – 3:30 pm		Break
3:30 pm – 4:30 pm		Graph Sparsification II: Barrier Functions and Rank-one Updates Nikhil Srivastava, Microsoft Research India

Wednesday, August 27th, 2014
9:30 am – 10:00 am		Coffee and Check-In
10:00 am – 11:00 am		Spectral Graph Theory III: Small-set Expanders, Clustering, and Eigenvalues Luca Trevisan, UC Berkeley
11:00 am – 11:30 am		Break
11:30 am – 12:30 pm		Graph Sparsification III: Interlacing Polynomials and Ramanujan Graphs of Every Degree Nikhil Srivastava, Microsoft Research India
12:30 pm – 2:00 pm		Lunch
2:00 pm – 3:00 pm		Semidefinite Programming Hierarchies I: Convex Relaxations for Hard Optimization Problems David Steurer, Cornell University
3:00 pm – 3:30 pm		Break
3:30 pm – 4:30 pm		Laplacian Systems and Electrical Flows I: Intro to Laplacian Systems, Iterative Methods, and Preconditioning Jon Kelner, Massachusetts Institute of Technology

Thursday, August 28th, 2014
9:30 am – 10:00 am		Coffee and Check-In
10:00 am – 11:00 am		Laplacian Systems and Electrical Flows II: Solving Laplacian Systems Using Recursive Preconditioning Jon Kelner, Massachusetts Institute of Technology
11:00 am – 11:30 am		Break
11:30 am – 12:30 pm		Semidefinite Programming Hierarchies II: Hierarchies of Relaxations and their Strengths and Limitations David Steurer, Cornell University
12:30 pm – 2:00 pm		Lunch
2:00 pm – 3:00 pm		Laplacian Systems and Electrical Flows III: A Simple, Combinatorial Solver without Recursive Preconditioning Jon Kelner, Massachusetts Institute of Technology
3:00 pm – 3:30 pm		Break
3:30 pm – 4:30 pm		Electrical Flows, Optimization, and New Approaches to the Maximum Flow Problem I: Electrical Flows as a New Primitive for Graph Algorithms Aleksander Mądry, École Polytechnique Fédérale de Lausanne

Friday, August 29th, 2014
9:30 am – 10:00 am		Coffee and Check-In
10:00 am – 11:00 am		Electrical Flows, Optimization, and New Approaches to the Maximum Flow Problem II: Approximating Maximum Flow with Electrical Flows Aleksander Mądry, École Polytechnique Fédérale de Lausanne
11:00 am – 11:30 am		Break
11:30 am – 12:30 pm		Semidefinite Programming Hierarchies III: Applications of the Sum-of-squares Method David Steurer, Cornell University
12:30 pm – 2:00 pm		Lunch
2:00 pm – 3:00 pm		Electrical Flows, Optimization, and New Approaches to the Maximum Flow Problem III: Maximum Flows and Interior-point Methods Aleksander Mądry, École Polytechnique Fédérale de Lausanne