Files in this item



application/pdfNaman_Agarwal.pdf (648kB)
(no description provided)PDF


Title:Unique Games Conjecture : the Boolean Hypercube and connections to graph lifts
Author(s):Agarwal, Naman
Advisor(s):Kolla, Alexandra
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Unique Games Conjecture
Boolean Hypercube
Graph Lifts
Ramanujan graphs
Spectral Graph Theory
Hardness of Approximation
Integrality Gaps
Semi-definite Programming
Abstract:In this thesis we consider two questions motivated by the Unique Games Conjecture . The first question is concerned with the validity of the Unique Games Conjecture when the constraint graph is restricted to the Boolean Hypercube. The Boolean Hypercube is a well studied graph family on which existing spectral methods fail to achieve a sub exponential time bound. We initiate the study of the behaviour of the standard semi-definite program on the Hypercube. We construct an almost optimal integrality gap instance on the Hypercube for the Goemans-Williamson semidefinite program (SDP) for Max-2-LIN(\Z_2). We conjecture that augmenting the SDP with triangle inequalities makes the SDP exact upto constants on the Hypercube. We further establish connections between the integrality gap of the SDP and Mutlicommodity flow-cut gaps which may lead to an understanding of the behaviour of the SDP on general families of graphs. As a quick corollary we establish that the SDP is exact for planar graphs. The second question is concerned with spectrum of label extended graphs of Unique Games instances. Such graphs have been extensively studied under the name of Graph Lifts. The main motivation for studying lifts has been understanding Ramanujan expander graphs via two key questions: Is a ``typical'' lift of an expander graph also an expander; and how can we (efficiently) construct Ramanujan expanders using lifts? In our work we continue the study of Graph Lifts and show that, for random shift k-lifts, if all the nontrivial eigenvalues of a d-regular graph G are at most lambda in absolute value, then with high probability depending only on the number n of nodes of G (and not on k), the absolute value of every nontrivial eigenvalue of the lift is at most Oh(\lambda). This improves upon factors of log(d) in the case when k=2. Other results on random lifts have focused on the case when k too infinity making their results asymptotically true with high probability in the degree of the lift k. To the best of our knowledge, our result is the first upperbound on spectra of lifts for bounded k > 2. Our result in particular implies that a typical small lift of a Ramanujan graph is almost Ramanujan, and we believe it will prove crucial in constructing large Ramanujan expanders of all degrees. We also establish a novel characterization of the spectrum of shift lifts by the spectrum of certain k symmetric matrices, that generalize the signed adjacency matrix. We believe that this characterization is of independent interest.
Issue Date:2014-05-30
Rights Information:Copyright 2014 Naman Agarwal
Date Available in IDEALS:2014-05-30
Date Deposited:2014-05

This item appears in the following Collection(s)

Item Statistics