NDLI: Spectral Algorithms for Unique Games

Content Provider	Springer Nature Link
Author	Kolla, Alexandra
Copyright Year	2011
Abstract	We give a new algorithm for Unique Games which is based on purely spectral techniques, in contrast to previous work in the area, which relies heavily on semidefinite programming (SDP). Given a highly satisfiable instance of Unique Games, our algorithm is able to recover a good assignment. The approximation guarantee depends only on the completeness of the game, and not on the alphabet size, while the running time depends on spectral properties of the Label-Extended graph associated with the instance of Unique Games.We further show that on input the integrality gap instance of Khot and Vishnoi, our algorithm runs in quasi-polynomial time and decides that the instance is highly unsatisfiable. Notably, when run on this instance, the standard SDP relaxation of Unique Games fails. As a special case, we also re-derive a polynomial time algorithm for Unique Games on expander constraint graphs.The main ingredient of our algorithm is a technique to effectively use the full spectrum of the underlying graph instead of just the second eigenvalue, which is of independent interest. The question of how to take advantage of the full spectrum of a graph in the design of algorithms has been often studied, but no significant progress was made prior to this work.
Starting Page	177
Ending Page	206
Page Count	30
File Format	PDF
ISSN	10163328
Journal	Computational complexity
Volume Number	20
Issue Number	2
e-ISSN	14208954
Language	English
Publisher	SP Birkhäuser Verlag Basel
Publisher Date	2011-07-12
Publisher Place	Basel
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Unique games graph spectra algorithms Algorithm Analysis and Problem Complexity Computational Mathematics and Numerical Analysis
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computational Theory and Mathematics Computational Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A parallel repetition theorem for entangled projection games

Derandomizing Arthur–Merlin Games using Hitting Sets

Approximation Resistant Predicates from Pairwise Independence

ON THE HARDNESS OF APPROXIMATING MULTICUT AND SPARSEST-CUT

Parameterized Proof Complexity

Quantum Arthur–Merlin games

Rank-one quantum games

Basis Collapse in Holographic Algorithms

Extractors for varieties

Spectral Algorithms for Unique Games

Similar Documents

A parallel repetition theorem for entangled projection games

Derandomizing Arthur–Merlin Games using Hitting Sets

Approximation Resistant Predicates from Pairwise Independence

ON THE HARDNESS OF APPROXIMATING MULTICUT AND SPARSEST-CUT

Parameterized Proof Complexity

Quantum Arthur–Merlin games

Rank-one quantum games

Basis Collapse in Holographic Algorithms

Extractors for varieties

Spectral Algorithms for Unique Games