Alexandra Kolla

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2010-7

January 23, 2010

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-7.pdf

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 textit{Unique Games} conjecture ({sf UGC}) cite{KhotUCSP}, whose validity is one of the most central open problems in computational complexity theory. We show that {sf UGC} is textit{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 textit{graph sparsification}. We say that a graph $H$ is a textit{sparsifier} for a graph $G$ if the respective graph Laplacians of the two graphs satisfy $x^TLa_H x approx x^TLa_G x$ for all vectors $x$. Given a union of two graphs $G+W$, we show how to choose a sparse subgraph $W' subseteq 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 textit{ultrasparsifiers} for every graph, which can be used as good graph-theoretic textit{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 $Omega(log log N)$ 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. paragraph{} 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.

Advisors: Umesh Vazirani

---

BibTeX citation:

@phdthesis{Kolla:EECS-2010-7,
    Author= {Kolla, Alexandra},
    Title= {Merging Techniques for Combinatorial Optimization: Spectral graph Theory and Semidefinite Programming},
    School= {EECS Department, University of California, Berkeley},
    Year= {2010},
    Month= {Jan},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-7.html},
    Number= {UCB/EECS-2010-7},
    Abstract= { 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 textit{Unique Games} conjecture ({sf UGC}) cite{KhotUCSP}, whose validity is one of the most central open problems in computational complexity theory. We show that {sf UGC} is textit{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 textit{graph sparsification}. We say that a graph $H$ is a textit{sparsifier} for a graph $G$ if the respective graph Laplacians of the two graphs satisfy $x^TLa_H x approx x^TLa_G x$ for all vectors $x$. Given a union of two graphs $G+W$, we show how to choose a sparse subgraph $W' subseteq 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 textit{ultrasparsifiers} for every graph, which can be used as good graph-theoretic textit{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 $Omega(log log N)$ 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.
paragraph{} 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.},
}

EndNote citation:

%0 Thesis
%A Kolla, Alexandra 
%T Merging Techniques for Combinatorial Optimization: Spectral graph Theory and Semidefinite Programming
%I EECS Department, University of California, Berkeley
%D 2010
%8 January 23
%@ UCB/EECS-2010-7
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-7.html
%F Kolla:EECS-2010-7