University of Illinois Urbana-Champaign

Unique Games Conjecture : the Boolean Hypercube and connections to graph lifts

Agarwal, Naman

Content Files
Naman_Agarwal.pdf

Permalink

https://hdl.handle.net/2142/49366

Description

Title
Unique Games Conjecture : the Boolean Hypercube and connections to graph lifts
Author(s)
Agarwal, Naman
Issue Date
2014-05-30T16:40:22Z
Director of Research (if dissertation) or Advisor (if thesis)
Kolla, Alexandra
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
M.S.
Degree Level
Thesis
Date of Ingest
2014-05-30T16:40:22Z
Keyword(s)
  • Unique Games Conjecture
  • Boolean Hypercube
  • MAX-LIN
  • 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.
Graduation Semester
2014-05
Permalink
http://hdl.handle.net/2142/49366
Copyright and License Information
Copyright 2014 Naman Agarwal

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Computer Science
Dissertations and Theses from the Siebel School of Computer Science