About
Spectral graph theory is a field based on using linear algebraic perspectives to study graphs, and, conversely, on using graph-theoretic ideas in linear algebra. In the past decade, it has had a major impact on theoretical computer science and in mathematics, as these connections have proven extremely rich. In algorithms and optimization, spectral graph theory has been central in the development of fast algorithms for polynomial-time solvable problems and in the field of the approximation algorithms for NP-hard problems.
This symposium will cover connections between spectral graph theory and a wide range of topics in algorithms and optimization. Nikhil Srivastava will talk of lower bounds for graph sparsification, showing limits to how much the information in a graph can be compressed without introducing too much error. Luca Trevisan will discuss generalizations of Cheeger's famous inequality relating the second eigenvalue of the Laplacian matrix of a graph to its sparsest cuts. Amin Saberi will talk of recent work on approximating the permanent of a PSD matrix, a #P-hard problem, and give some applications. Preconditioning has played a crucial role in the development of fast algorithms for computing electrical flow and approximate undirected maximum flow, and Jonah Sherman will talk of generalizations of preconditioning that lead to nearly-linear time algorithms for approximate undirected, unit capacity min cost flow. Soledad Villar will teach us about classical results that connect k-means clustering and spectral clustering with problems like non-negative factorization and normalized cuts, before considering relaxations of these problems based on spectral methods, semidefinite optimization, and manifold optimization.
Invited Speakers:
Amin Saberi (Stanford University), Jonah Sherman (UC Berkeley), Nikhil Srivastava (UC Berkeley), Luca Trevisan (UC Berkeley) and Soledad Villar (NYU)
Chairs/Organizers
