Seminar on Laplacian systems and their applications, Spring 20/21

Haim Kaplan, Wednesdays 18-20

Please pick 3-4 options for your lecture, rank them, and send them to me asap.

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]


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)