Recently Added

Graph and Subgraph Sparsification and its Implications to Linear System Solving and Transforming Graphs into Expanders

Alexandra Kolla
Institute for Advanced Study
November 10, 2009

I will first give an overview of several constructions of graph sparsifiers and their properties. I will then present a method of sparsifying a subgraph W of a graph G with optimal number of edges and talk about the implications of subgraph sparsification in constructing nearly-optimal ultrasparsifiers and optimizing the algebraic connectivity of a graph by adding few edges.

The talk is based on joint work with Makarychev,Saberi,Teng.

Constructions of Expanders Using Group Theory

Martin Kassabov
Cornell University; von Neumann Fellow, School of Mathematics
November 3, 2009

I will survey some constructions of expander graphs using variants of Kazhdan property T . First, I describe an approach to property T using bounded generation and then I will describe a recent method based on the geometric properties of configurations of subspaces in a finite dimensional Euclidean space.