2026-09-19T08:17:45Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/49366 2023-07-11 col_2142_5131 col_2142_10761 com_2142_5130 com_2142_10755 com_2142_234

Kolla, Alexandra Agarwal, Naman 2014-05-30T16:40:22Z 2014-05-30T16:40:22Z 2014-05 2014-05-30T16:40:22Z 2014-05 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. Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2014-04-29T13:40:26Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 4 FigureSDP1.png: 55389 bytes, checksum: 19b9b4deef107a3254aaa946a844df92 (MD5) ms_thesis.bib: 17347 bytes, checksum: be982c6be0bd2231a70244008c0ec4b4 (MD5) backup.tex: 172252 bytes, checksum: 3b26c2e426b7c2505988bff695e6b520 (MD5) Agarwal_Naman.pdf: 648331 bytes, checksum: aa6dafa7fcba0f62d07a5f8c668a596a (MD5) Made available in DSpace on 2014-05-30T16:40:22Z (GMT). No. of bitstreams: 5 Naman_Agarwal.pdf: 648331 bytes, checksum: aa6dafa7fcba0f62d07a5f8c668a596a (MD5) FigureSDP1.png: 55389 bytes, checksum: 19b9b4deef107a3254aaa946a844df92 (MD5) ms_thesis.bib: 17347 bytes, checksum: be982c6be0bd2231a70244008c0ec4b4 (MD5) backup.tex: 172252 bytes, checksum: 3b26c2e426b7c2505988bff695e6b520 (MD5) license.txt: 4063 bytes, checksum: cc5f332296e53ed0dce757b06f7c884a (MD5) http://hdl.handle.net/2142/49366 en Copyright 2014 Naman Agarwal Unique Games Conjecture Boolean Hypercube MAX-LIN Graph Lifts Ramanujan graphs Spectral Graph Theory Hardness of Approximation Integrality Gaps Semi-definite Programming Unique Games Conjecture : the Boolean Hypercube and connections to graph lifts text Computer Science 1434 Computer Science 0112 University of Illinois at Urbana-Champaign Thesis M.S. MS:Computer Science -UIUC 10KS0112MS