Abstracts

Algorithmic Spectral Graph Theory Boot Camp

Tuesday, August 26th, 2014

Spectral Graph Theory I: Introduction to Spectral Graph Theory
10:00 am–11:00 am
Speaker: Luca Trevisan, UC Berkeley

Spectral graph theory studies connections between combinatorial properties of graphs and the eigenvalues of matrices associated to the graph, such as the adjacency matrix and the Laplacian matrix.

Spectral graph theory has applications to the design and analysis of approximation algorithms for graph partitioning problems, to the study of random walks in graph, and to the construction of expander graphs. It also reveals connections between the above topics, and provides, for example, a way to use random walks to approximately solve graph partitioning problems.

In this series of lectures we will introduce the basics of spectral graph theory, we will prove the discrete Cheeger inequalities, and see them as (i) a way to approximate the sparsest cut problem, (ii) an approach to bound the mixing time of random walks, and (iii) a way to certify expansion in graphs. We will then consider various generalizations of this result, such as higher-order Cheeger inequalities, a Cheeger-like inequality for the largest eigenvalue of the Laplacian, and the expander mixing lemma and its inverse. Each of these more advanced results will also be interpreted as the analysis of an approximation algorithm for a graph partitioning problem.

The second session of this talk will take place on Tuesday, August 26 from 2:00 pm – 3:00 pm; the third session of this talk will take place on Wednesday, August 27 from 10:00 am – 11:00 am.

Related Links

Lecture Notes on Expansion, Sparsest Cut, and Spectral Graph Theory
http://www.eecs.berkeley.edu/~luca/books/expanders.pdf

Graph Sparsification I: Sparsification via Effective Resistances
11:30 am–12:30 pm
Speaker: Nikhil Srivastava, Microsoft Research India

Approximating a given graph by a graph with fewer edges or vertices is called sparsification. The notion of approximation that is most relevant to this workshop is the spectral one, in which two graphs are considered close if their Laplacian matrices are close as linear operators. It turns out that spectral approximations exist for every weighted undirected graph and can often be computed very quickly; in the past few years this has become a useful and versatile primitive in designing efficient graph algorithms.

We will survey constructions of (weighted) spectral sparsifiers in various parameter regimes (polylogarithmic degree, constant degree, and beyond) and mention their applications. These constructions involve viewing a graph in three different ways: combinatorially, as an electrical circuit, and as a bunch of vectors. We will then describe a more recent method which shows that unweighted sparsifiers exist many cases; it is based on viewing the subgraphs of a graph as polynomials, and exploiting real-rootedness properties of their averages. This last technique is rather general and can be used to solve other problems outside graph theory, such as the Kadison-Singer problem.

Time permitting, we will also discuss more practical, streaming algorithms for sparsification, as well as the important special case when the input graph is the complete graph (whose sparsifiers are the ubiquitous expander graphs).

The second session of this talk will take place on Tuesday, August 26 from 3:30 pm – 4:30 pm; the third session of this talk will take place on Wednesday, August 27 from 11:30 am – 12:30 pm.

PDF icon Sparsification via Effective Resistances (slides)
Spectral Graph Theory II: Expanders and Eigenvalues
2:00 pm–3:00 pm
Speaker: Luca Trevisan, UC Berkeley

Spectral graph theory studies connections between combinatorial properties of graphs and the eigenvalues of matrices associated to the graph, such as the adjacency matrix and the Laplacian matrix.

Spectral graph theory has applications to the design and analysis of approximation algorithms for graph partitioning problems, to the study of random walks in graph, and to the construction of expander graphs. It also reveals connections between the above topics, and provides, for example, a way to use random walks to approximately solve graph partitioning problems.

In this series of lectures we will introduce the basics of spectral graph theory, we will prove the discrete Cheeger inequalities, and see them as (i) a way to approximate the sparsest cut problem, (ii) an approach to bound the mixing time of random walks, and (iii) a way to certify expansion in graphs. We will then consider various generalizations of this result, such as higher-order Cheeger inequalities, a Cheeger-like inequality for the largest eigenvalue of the Laplacian, and the expander mixing lemma and its inverse. Each of these more advanced results will also be interpreted as the analysis of an approximation algorithm for a graph partitioning problem.

The first session of this talk will take place on Tuesday, August 26 from 10:00 am – 11:00 am; the third session of this talk will take place on Wednesday, August 27 from 10:00 am – 11:00 am.

Related Links

Lecture Notes on Expansion, Sparsest Cut, and Spectral Graph Theory
http://www.eecs.berkeley.edu/~luca/books/expanders.pdf

Graph Sparsification II: Barrier Functions and Rank-one Updates
3:30 pm–4:30 pm
Speaker: Nikhil Srivastava, Microsoft Research India

Approximating a given graph by a graph with fewer edges or vertices is called sparsification. The notion of approximation that is most relevant to this workshop is the spectral one, in which two graphs are considered close if their Laplacian matrices are close as linear operators. It turns out that spectral approximations exist for every weighted undirected graph and can often be computed very quickly; in the past few years this has become a useful and versatile primitive in designing efficient graph algorithms.

We will survey constructions of (weighted) spectral sparsifiers in various parameter regimes (polylogarithmic degree, constant degree, and beyond) and mention their applications. These constructions involve viewing a graph in three different ways: combinatorially, as an electrical circuit, and as a bunch of vectors. We will then describe a more recent method which shows that unweighted sparsifiers exist many cases; it is based on viewing the subgraphs of a graph as polynomials, and exploiting real-rootedness properties of their averages. This last technique is rather general and can be used to solve other problems outside graph theory, such as the Kadison-Singer problem.

Time permitting, we will also discuss more practical, streaming algorithms for sparsification, as well as the important special case when the input graph is the complete graph (whose sparsifiers are the ubiquitous expander graphs).

The first session of this talk will take place on Tuesday, August 26 from 11:30 am – 12:30 pm; the third session of this talk will take place on Wednesday, August 27 from 11:30 am – 12:30 pm.

PDF icon Barrier Functions and Rank-one Updates (slides)

Wednesday, August 27th, 2014

Spectral Graph Theory III: Small-set Expanders, Clustering, and Eigenvalues
10:00 am–11:00 am
Speaker: Luca Trevisan, UC Berkeley

Spectral graph theory studies connections between combinatorial properties of graphs and the eigenvalues of matrices associated to the graph, such as the adjacency matrix and the Laplacian matrix.

Spectral graph theory has applications to the design and analysis of approximation algorithms for graph partitioning problems, to the study of random walks in graph, and to the construction of expander graphs. It also reveals connections between the above topics, and provides, for example, a way to use random walks to approximately solve graph partitioning problems.

In this series of lectures we will introduce the basics of spectral graph theory, we will prove the discrete Cheeger inequalities, and see them as (i) a way to approximate the sparsest cut problem, (ii) an approach to bound the mixing time of random walks, and (iii) a way to certify expansion in graphs. We will then consider various generalizations of this result, such as higher-order Cheeger inequalities, a Cheeger-like inequality for the largest eigenvalue of the Laplacian, and the expander mixing lemma and its inverse. Each of these more advanced results will also be interpreted as the analysis of an approximation algorithm for a graph partitioning problem.

The first session of this talk will take place on Tuesday, August 26 from 10:00 am – 11:00 am; the second session of this talk will take place on Tuesday, August 26 from 2:00 pm – 3:00 pm.

Related Links

Lecture Notes on Expansion, Sparsest Cut, and Spectral Graph Theory
http://www.eecs.berkeley.edu/~luca/books/expanders.pdf

Graph Sparsification III: Interlacing Polynomials and Ramanujan Graphs of Every Degree
11:30 am–12:30 pm
Speaker: Nikhil Srivastava, Microsoft Research India

Approximating a given graph by a graph with fewer edges or vertices is called sparsification. The notion of approximation that is most relevant to this workshop is the spectral one, in which two graphs are considered close if their Laplacian matrices are close as linear operators. It turns out that spectral approximations exist for every weighted undirected graph and can often be computed very quickly; in the past few years this has become a useful and versatile primitive in designing efficient graph algorithms.

We will survey constructions of (weighted) spectral sparsifiers in various parameter regimes (polylogarithmic degree, constant degree, and beyond) and mention their applications. These constructions involve viewing a graph in three different ways: combinatorially, as an electrical circuit, and as a bunch of vectors. We will then describe a more recent method which shows that unweighted sparsifiers exist many cases; it is based on viewing the subgraphs of a graph as polynomials, and exploiting real-rootedness properties of their averages. This last technique is rather general and can be used to solve other problems outside graph theory, such as the Kadison-Singer problem.

Time permitting, we will also discuss more practical, streaming algorithms for sparsification, as well as the important special case when the input graph is the complete graph (whose sparsifiers are the ubiquitous expander graphs).

The first session of this talk will take place on Tuesday, August 26 from 11:30 am – 12:30 pm; the second session of this talk will take place on Tuesday, August 26 from 3:30 pm – 4:30 pm.

PDF icon Interlacing Polynomials and Ramanujan Graphs of Every Degree (slides)
Semidefinite Programming Hierarchies I: Convex Relaxations for Hard Optimization Problems
2:00 pm–3:00 pm
Speaker: David Steurer, Cornell University

Convex programming relaxations achieve for a broad range of computationally hard optimization problems the best known approximation guarantees. For many such problems, stronger relaxations are the most promising approach to obtain better and potentially optimal guarantees. We will discuss systematic methods for devising increasingly stronger relaxations, both in the linear programming and semidefinite programming case, and how to reason about their guarantees. We will introduce the sum-of-squares method which is a conceptually simple meta-algorithm that unifies all existing relaxation methods. Finally, we will illustrate its connections to spectral methods, proof complexity, and real algebraic geometry and applications to quantum information, multilinear algebra, sparse recovery, and machine learning.

The second session of this talk will take place on Thursday, August 28 from 11:30 am – 12:30 pm; the third session of this talk will take place on Friday, August 29 from 11:30 am – 12:30 pm.

Laplacian Systems and Electrical Flows I: Intro to Laplacian Systems, Iterative Methods, and Preconditioning
3:30 pm–4:30 pm
Speaker: Jon Kelner, Massachusetts Institute of Technology

As illustrated by several other talks in this boot camp, the combinatorial properties of a graph are deeply connected to the linear algebraic properties of its Laplacian, and the ability to solve linear systems (and other algebraic problems) in graph Laplacians provides a powerful tool for probing the structure of a graph. As such, fast algorithms for solving Laplacian linear systems have found broad applications across both the theory and practice of computer science, playing a foundational role in scientific computing, machine learning, random processes, image processing, network analysis, and computational biology, among others. More recently, they have emerged as a powerful tool in the design of graph algorithms, enabling researchers to break longstanding algorithmic barriers for a wide range of fundamental graph problems.

Finding fast solvers for Laplacian systems has been an active area of research since the 1960s. This has culminated in recent algorithms that exploit the interplay between the combinatorial structure of a graph and the linear algebraic structure of its Laplacian to solve these systems in nearly-linear time. In this series of lectures, I will discuss the main ideas behind two such algorithms. I will begin by briefly describing classical iterative methods for general linear systems and the problems they encounter when applied to Laplacians. I will then introduce the techniques from spectral and combinatorial graph theory, graph algorithms, and iterative methods that allow us to overcome these problems and solve Laplacian systems in nearly-linear time.

The lectures will be self-contained and will not assume prior background in computational linear algebra.

The second session of this talk will take place on Thursday, August 28 from 10:00 am – 11:00 am; the third session of this talk will take place on Thursday, August 28 from 2:00 pm – 3:00 pm.

Thursday, August 28th, 2014

Laplacian Systems and Electrical Flows II: Solving Laplacian Systems Using Recursive Preconditioning
10:00 am–11:00 am
Speaker: Jon Kelner, Massachusetts Institute of Technology

As illustrated by several other talks in this boot camp, the combinatorial properties of a graph are deeply connected to the linear algebraic properties of its Laplacian, and the ability to solve linear systems (and other algebraic problems) in graph Laplacians provides a powerful tool for probing the structure of a graph. As such, fast algorithms for solving Laplacian linear systems have found broad applications across both the theory and practice of computer science, playing a foundational role in scientific computing, machine learning, random processes, image processing, network analysis, and computational biology, among others. More recently, they have emerged as a powerful tool in the design of graph algorithms, enabling researchers to break longstanding algorithmic barriers for a wide range of fundamental graph problems.

Finding fast solvers for Laplacian systems has been an active area of research since the 1960s. This has culminated in recent algorithms that exploit the interplay between the combinatorial structure of a graph and the linear algebraic structure of its Laplacian to solve these systems in nearly-linear time. In this series of lectures, I will discuss the main ideas behind two such algorithms. I will begin by briefly describing classical iterative methods for general linear systems and the problems they encounter when applied to Laplacians. I will then introduce the techniques from spectral and combinatorial graph theory, graph algorithms, and iterative methods that allow us to overcome these problems and solve Laplacian systems in nearly-linear time.

The lectures will be self-contained and will not assume prior background in computational linear algebra.

The first session of this talk will take place on Wednesday, August 27 from 3:30 pm – 4:30 pm; the third session of this talk will take place on Thursday, August 28 from 2:00 pm – 3:00 pm.

Semidefinite Programming Hierarchies II: Hierarchies of Relaxations and their Strengths and Limitations
11:30 am–12:30 pm
Speaker: David Steurer, Cornell University

Convex programming relaxations achieve for a broad range of computationally hard optimization problems the best known approximation guarantees. For many such problems, stronger relaxations are the most promising approach to obtain better and potentially optimal guarantees. We will discuss systematic methods for devising increasingly stronger relaxations, both in the linear programming and semidefinite programming case, and how to reason about their guarantees. We will introduce the sum-of-squares method which is a conceptually simple meta-algorithm that unifies all existing relaxation methods. Finally, we will illustrate its connections to spectral methods, proof complexity, and real algebraic geometry and applications to quantum information, multilinear algebra, sparse recovery, and machine learning.

The first session of this talk will take place on Wednesday, August 27 from 2:00 pm – 3:00 pm; the third session of this talk will take place on Friday, August 29 from 11:30 am – 12:30 pm.

Laplacian Systems and Electrical Flows III: A Simple, Combinatorial Solver without Recursive Preconditioning
2:00 pm–3:00 pm
Speaker: Jon Kelner, Massachusetts Institute of Technology

As illustrated by several other talks in this boot camp, the combinatorial properties of a graph are deeply connected to the linear algebraic properties of its Laplacian, and the ability to solve linear systems (and other algebraic problems) in graph Laplacians provides a powerful tool for probing the structure of a graph. As such, fast algorithms for solving Laplacian linear systems have found broad applications across both the theory and practice of computer science, playing a foundational role in scientific computing, machine learning, random processes, image processing, network analysis, and computational biology, among others. More recently, they have emerged as a powerful tool in the design of graph algorithms, enabling researchers to break longstanding algorithmic barriers for a wide range of fundamental graph problems.

Finding fast solvers for Laplacian systems has been an active area of research since the 1960s. This has culminated in recent algorithms that exploit the interplay between the combinatorial structure of a graph and the linear algebraic structure of its Laplacian to solve these systems in nearly-linear time. In this series of lectures, I will discuss the main ideas behind two such algorithms. I will begin by briefly describing classical iterative methods for general linear systems and the problems they encounter when applied to Laplacians. I will then introduce the techniques from spectral and combinatorial graph theory, graph algorithms, and iterative methods that allow us to overcome these problems and solve Laplacian systems in nearly-linear time.

The lectures will be self-contained and will not assume prior background in computational linear algebra.

The first session of this talk will take place on Wednesday, August 27 from 3:30 pm – 4:30 pm; the second session of this talk will take place on Thursday, August 28 from 10:00 am – 11:00 am.

Electrical Flows, Optimization, and New Approaches to the Maximum Flow Problem I: Electrical Flows as a New Primitive for Graph Algorithms
3:30 pm–4:30 pm
Speaker: Aleksander Mądry, École Polytechnique Fédérale de Lausanne

Graphs are ubiquitous in all modern sciences. This motivates a need for algorithmic tools that are capable of analyzing and computing on graphs in an efficient manner. A need that is even more pressing now that the graphs we are dealing with tend to be massive, rendering traditional methods no longer adequate. 

In this talk, I will discuss a recent progress on the maximum flow problem and use it as an illustration of a broader emerging theme in graph algorithms that employs optimization methods as an algorithmic bridge between our combinatorial and spectral understanding of graphs. 

I will also briefly outline how this line of work brings a new perspective on some of the core continuous optimization primitives - most notably, interior-point methods.

The second session of this talk will take place on Friday, August 29 from 10:00 am – 11:00 am; the third session of this talk will take place on Friday, August 29 from 2:00 pm – 3:00 pm.

PDF icon Electrical Flows as a New Primitive for Graph Algorithms (slides)

Friday, August 29th, 2014

Electrical Flows, Optimization, and New Approaches to the Maximum Flow Problem II: Approximating Maximum Flow with Electrical Flows
10:00 am–11:00 am
Speaker: Aleksander Mądry, École Polytechnique Fédérale de Lausanne

Graphs are ubiquitous in all modern sciences. This motivates a need for algorithmic tools that are capable of analyzing and computing on graphs in an efficient manner. A need that is even more pressing now that the graphs we are dealing with tend to be massive, rendering traditional methods no longer adequate. 

In this talk, I will discuss a recent progress on the maximum flow problem and use it as an illustration of a broader emerging theme in graph algorithms that employs optimization methods as an algorithmic bridge between our combinatorial and spectral understanding of graphs. 

I will also briefly outline how this line of work brings a new perspective on some of the core continuous optimization primitives - most notably, interior-point methods.

The first session of this talk will take place on Thursday, August 28 from 3:30 pm – 4:30 pm; the third session of this talk will take place on Friday, August 29 from 2:00 pm – 3:00 pm.

PDF icon Approximating Maximum Flow with Electrical Flows (slides)
Semidefinite Programming Hierarchies III: Applications of the Sum-of-squares Method
11:30 am–12:30 pm
Speaker: David Steurer, Cornell University

Convex programming relaxations achieve for a broad range of computationally hard optimization problems the best known approximation guarantees. For many such problems, stronger relaxations are the most promising approach to obtain better and potentially optimal guarantees. We will discuss systematic methods for devising increasingly stronger relaxations, both in the linear programming and semidefinite programming case, and how to reason about their guarantees. We will introduce the sum-of-squares method which is a conceptually simple meta-algorithm that unifies all existing relaxation methods. Finally, we will illustrate its connections to spectral methods, proof complexity, and real algebraic geometry and applications to quantum information, multilinear algebra, sparse recovery, and machine learning.

The first session of this talk will take place on Wednesday, August 27 from 2:00 pm – 3:00 pm; the second session of this talk will take place on Thursday, August 28 from 11:30 am – 12:30 pm.

Electrical Flows, Optimization, and New Approaches to the Maximum Flow Problem III: Maximum Flows and Interior-point Methods
2:00 pm–3:00 pm
Speaker: Aleksander Mądry, École Polytechnique Fédérale de Lausanne

Graphs are ubiquitous in all modern sciences. This motivates a need for algorithmic tools that are capable of analyzing and computing on graphs in an efficient manner. A need that is even more pressing now that the graphs we are dealing with tend to be massive, rendering traditional methods no longer adequate. 

In this talk, I will discuss a recent progress on the maximum flow problem and use it as an illustration of a broader emerging theme in graph algorithms that employs optimization methods as an algorithmic bridge between our combinatorial and spectral understanding of graphs. 

I will also briefly outline how this line of work brings a new perspective on some of the core continuous optimization primitives - most notably, interior-point methods.

The first session of this talk will take place on Thursday, August 28 from 3:30 pm – 4:30 pm; the second session of this talk will take place on Friday, August 29 from 10:00 am – 11:00 am.

PDF icon Maximum Flows and Interior-point Methods (slides)