UC Berkeley

In this thesis, we study three problems related to expanders, whose analysis involves understanding the intimate connection between expanders, spectra and semidefinite programming. Our first result is related to Khot's Unique Games conjecture (UGC), whose validity is one of the most central open problems in computational complexity theory. We show that UGC is false on expander graphs. This result, in particular, rules out a natural way of proving hardness of approximation for SPARSEST CUT. Our second result is in the area of graph sparsification. We say that a graph H is a sparsifier for a graph G if the respective graph Laplacians of the two graphs satisfy x^TL_Hx &le x^TL_Gx, for all vectors x. Given a union of two graphs G+W, we show how to choose a sparse subgraph W' of W so that G+W' is a good sparsifier for G+W. We apply the result to optimizing the algebraic connectivity of a graph by adding very few edges. We also show how to use this result in order to create optimal ultrasparsifiers for every graph, which can be used as good graph theoretic preconditioners for symmetric, positive semidefinite, diagonally dominant linear systems. Lastly, we study the integrality gap of the well known Sparsest Cut semidefinite program. We present a simple construction and analysis of an ­O(log logN) integrality gap for Sparsest Cut while our gap instance, vector solution, and analysis are somewhat simpler and more intuitive than those which appear in the literature.

Our techniques use tools both from the area of semidefinite programming and spectral graph theory. This is not surprising since, when delving into the beautiful theory underlying spectra and SDPs, one finds that they are deeply connected in more ways than one.

Semidefinite programs are nothing but linear programs with variables representing entries of a matrix, together with eigenvalue bounds for that matrix and could, therefore capture the spectral expansion of a graph. Similarly, most of eigenvalue optimization problems can

be cast as SDPs, which leads to developing semidefinite programming based algorithms for a plethora of other important graph problems. In this thesis we further explore the connections between expansion, spectra and SDPs by applying them to solving these three

problems described above.