How to play unique games on expanders

Konstantin Makarychev*, Yury Makarychev

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations

Abstract

In this paper, we improve a result by Arora, Khot, Kolla, Steurer, Tulsiani, and Vishnoi on solving the Unique Games problem on expanders. Given a (1-ε)-satisfiable instance of Unique Games with the constraint graph G, our algorithm finds an assignment satisfying at least a 1-C ε/hG fraction of all constraints if ε<cλG where h G is the edge expansion of G, λG is the second smallest eigenvalue of the Laplacian of G, and C and c are some absolute constants.

Original languageEnglish (US)
Title of host publicationApproximation and Online Algorithms - 8th International Workshop, WAOA 2010, Revised Papers
Pages190-200
Number of pages11
DOIs
StatePublished - 2011
Event8th International Workshop on Approximation and Online Algorithms, WAOA 2010 - Liverpool, United Kingdom
Duration: Sep 9 2010Sep 10 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6534 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other8th International Workshop on Approximation and Online Algorithms, WAOA 2010
CountryUnited Kingdom
CityLiverpool
Period9/9/109/10/10

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'How to play unique games on expanders'. Together they form a unique fingerprint.

Cite this