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

Agarwal, Naman

Permalink

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

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

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