Some students in my department this quarter hosted a reading group on quantum computing. Quantum computing is becoming more and more relevant and the topic attracted the participation of a diverse group of researchers. The best way to handle the scope of the topic and diversity of the participants was to invite volunteer speakers to give talks on the quantum analog of their own research area — “Quantum Circuit Lower Bounds,” “Quantum Game Theory,” and “QPSPACE” were among some of the topics. Naturally, I saw this as a great opportunity to understand more about quantum spectral graph theory. In this post I will outline some basic definitions and properties of quantum graphs, and as a follow up to my previous post on the connections between spectral geometry and graph theory, discuss isospectral properties of discrete and quantum graphs. Continue reading

# Author Archives: Olivia

# The Geometric Origins of Spectral Graph Theory

Spectral graph theory is the study of the intimate relationship of eigenvalues to different properties of graphs. Most typically the eigenvalues are associated to eigenfunctions of matrices associated to graphs known as Laplacians. Let $latex G = (V, E)$ be a weighted or unweighted undirected graph (there are simple extensions to directed graphs for many problems). Let $latex A$ be the adjacency matrix and let $latex D$ be the diagonal degree matrix, that is, $latex (D)_{ii} = d_i$, the degree of vertex $latex i$. Then a common definition for the Laplacian is $latex L = D-A$.

As I develop in my research in spectral graph theory, I am consistently amazed by the truth that many results in spectral graph theory can be seen as discrete analogues to results in spectral geometry. I am not accustomed to thinking of graphs as geometric objects, but in fact graph Laplacian matrices are nicely related to Laplace operators on Riemannian manifolds. In this post, I’d like to discuss a few of these relationships. Continue reading

# Software Packages for Theoreticians by Theoreticians

Brown University’s ICERM recently hosted a workshop titled “Electrical Flows, Graph Laplacians, and Algorithms,” where top researchers convened to present and discuss their recent progress in spectral graph theory and algorithms. Richard Peng opened up the workshop with an overview talk on efficient solvers for linear systems with graph Laplacians as the coefficient matrix. He presented a thorough history of the topic and set the stage for the variety of technical talks on fast algorithms for graph sparsification, spectral clustering, computing max flow, as well as a variety of other local and approximation algorithms.

His talk (as well as many of the rest) are archived and available thanks to ICERM. I will focus on one highlight – a point that resonated with the conclusion of Richard Peng’s talk – a call for more software implementing these new, fast algorithms. In this light, I’d like to briefly discuss some of the software packages out there for spectral graph theory and the analysis of large graphs being developed by theoreticians active in the area. Continue reading

# The Evolution of Local Graph Partitioning

As a follow-up to my previous post on the discussion of where theory and experimentation meet in the study of large-scale networks, I would like to discuss in more detail one of the empirically best-performing algorithms which also has a sound theoretical background: spectral partitioning. In this post I will examine the history of the problem, outline some key results, and present some future ideas for the problem. Continue reading

# Laying the Foundation for a Common Ground

This week, the Simons Institute hosted a workshop entitled *Unifying Theory and Experiment for Large-Scale Networks*. The goal of the workshop is to bring together researchers involved in various large networks problems to discuss both the theoretical models and the empirical process for testing and validating them. Even further, the “unifying” in the title suggests a forum on where the ends of the spectrum may meet.