**We will focus on some algorithmic aspects of spectral or algebraic graph
theory. We will mainly discuss Laplacian systems, how to solve them, and their
applications. Spielman and Teng
in their seminal works:**

**· ****Spielman**** and Teng, Nearly-Linear
Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant
Linear Systems, Siam journal on Matrix analysis and applications, 2006.**

**· ****Spielman**** and Teng, A
Local Clustering Algorithm for Massive Graphs and Its Application to Nearly
Linear Time Graph Partitioning, Siam journal on computing 2013**

**· ****Spielman**** and Teng, Spectral Sparsification of Graphs, Siam journal on computing
2014.**

**were the first that showed how to solve Laplacian systems in near
linear time. Their work has been subsequently improved and simplified in
several papers, some of which we will touch in this seminar. **

**Our main guiding text will be the short monograph:**

**·
****Vishnoi****, Lx
= b, Laplacian Solvers and Their Algorithmic Application ****[V]**

**Additional good sources are **

**· ****Trevisan****, Lecture Notes on Expansion,
Sparsest Cut, and Spectral Graph Theory, 2016 ****[T]**

**· ****Kannan, Vempala, Spectral
Algorithms, 2009**

**· ****Godsil****, Royle, Algebraic Graph Theory,
2001, Springer (approach me to borrow a copy) ****[GR]**

**Schedule **

**1) ****(Mar 3) ****An
introductory lecture **

**2) ****(Mar 10)**** Colbourn, Day, Nel, Unranking and ranking spanning trees of a graph, You
can also use use Section 13.2 of the book by Godsil and Royle and the lecture
notes of Shayan Ovies Gharan
(lectures
1+2). ****Amit Amram, ****(video and slides)**

**3) ****(Mar 17)
Graph**** partitioning,
conductance, Fiedler's Algorithm (Chapter 5+6 of [V], 4+5 in [T]. Yossi Khayet (video and slides)**

**4) ****(Apr 7) Balanced**** cuts and computing
the second eigenvalue (Chapters 7-8 of [V], Chapter 9 of [T]). Ron Cogan (video and slides)**

**5) ****(Apr
21)**** ****Benczur**** and Karger, Randomized Approximation
Schemes for Cuts and Flows in Capacitated Graphs, Siam journal on computing
2015, Neta Ezra (video and slides)**

**6) ****(April
28)**** ****Spielman**** and Srivastava, Graph
Sparsification by Effective Resistances, Siam
journal on Computing 2011 (Chapters 10, 11 in [V]), Yoav Yaron (video and slides)**

**7) ****(May 5****)
Christiano,
Kelner,
Madry, Spielman, Teng, Electrical
flows, Laplacian systems, and faster approximation of maximum flow in
undirected graphs, STOC 2011 (Chapters 12 in [V]), Yuval
Fuks (video and slides)**

**8) ****(May 12) ****Iterative
methods: Gradient descent and conjugate gradient ****(Chapters 15,16 in [V]), Sar Hamam
(video and slides)**

9) **(May 19)**
Preconditioning, tree preconditioners **(Chapters 17,13 in [V]), Tom
Verbin (video and slides)**

10) ** (May 26****) Elkin, Emek, Spielman,Teng****, ****Lower-Stretch
Spanning Trees, Siam journal on computing 2008 (See also Papp),
****Yahav**** Dascal ****(video
and slides)**

**11) **** (June 2) ****Koutis****, Miller, and Peng, Approaching Optimality for
Solving SDD Linear Systems, Siam journal on computing, 2014 ****(Chapters 18 in [V]), Eldad Peretz (video
and slides)**

**12) **** (June 9) Kelner, Orecchia, Sidford, Zhu, ****A Simple,
Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time ****(part 1) ****(Chapters 14 in
[V]), Itay Cohen (video
and slides)**

**13) **** ****(June
16) ****A Simple, Combinatorial
Algorithm for Solving SDD Systems in Nearly-Linear Time ****(part 2) ****Ishay**** Golinski ****(video
and slides)**