{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/49366"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/49366","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Unique Games Conjecture : the Boolean Hypercube and connections to graph lifts","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Agarwal, Naman"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Kolla, Alexandra"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-05-30T16:40:22Z","date_published":"2014-05-30T16:40:22Z","updated_at":"2026-07-22T22:25:38Z","subjects":["Unique Games Conjecture","Boolean Hypercube","MAX-LIN","Graph Lifts","Ramanujan graphs","Spectral Graph Theory","Hardness of Approximation","Integrality Gaps","Semi-definite Programming"],"languages":["en"],"rights":["Copyright 2014 Naman Agarwal"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/49366","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Kolla, Alexandra"]},{"key":"dc:creator","label":"Author","values":["Agarwal, Naman"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-05-30T16:40:22Z","2014-05"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Unique Games Conjecture","Boolean Hypercube","MAX-LIN","Graph Lifts","Ramanujan graphs","Spectral Graph Theory","Hardness of Approximation","Integrality Gaps","Semi-definite Programming"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2014 Naman Agarwal"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/49366"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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)"]},{"key":"dc:title","label":"Title","values":["Unique Games Conjecture : the Boolean Hypercube and connections to graph lifts"]}]}],"canonical_facts":{"dc:contributor":["Kolla, Alexandra"],"dc:creator":["Agarwal, Naman"],"dc:date":["2014-05-30T16:40:22Z","2014-05"],"dc:description":["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)"],"dc:identifier":["http://hdl.handle.net/2142/49366"],"dc:language":["en"],"dc:rights":["Copyright 2014 Naman Agarwal"],"dc:subject":["Unique Games Conjecture","Boolean Hypercube","MAX-LIN","Graph Lifts","Ramanujan graphs","Spectral Graph Theory","Hardness of Approximation","Integrality Gaps","Semi-definite Programming"],"dc:title":["Unique Games Conjecture : the Boolean Hypercube and connections to graph lifts"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:38Z"}