SDP gaps for 2-to-1 and other label-cover variants

Venkatesan Guruswami, Subhash Khot, Ryan O'Donnell, Preyas Popat, Madhur Tulsiani, Yi Wu

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

Abstract

In this paper we present semidefinite programming (SDP) gap instances for the following variants of the Label-Cover problem, closely related to the Unique Games Conjecture: (i) 2-to-1 Label-Cover; (ii) 2-to-2 Label-Cover; (iii) α-constraint Label-Cover. All of our gap instances have perfect SDP solutions. For alphabet size K, the integral optimal solutions have value: (i) O(1/logK); (ii) O(1/logK); (iii) O(1/logK). Prior to this work, there were no known SDP gap instances for any of these problems with perfect SDP value and integral optimum tending to 0.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings
Pages617-628
Number of pages12
EditionPART 1
DOIs
StatePublished - 2010
Event37th International Colloquium on Automata, Languages and Programming, ICALP 2010 - Bordeaux, France
Duration: Jul 6 2010Jul 10 2010

Publication series

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

Other

Other37th International Colloquium on Automata, Languages and Programming, ICALP 2010
CountryFrance
CityBordeaux
Period7/6/107/10/10

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'SDP gaps for 2-to-1 and other label-cover variants'. Together they form a unique fingerprint.

Cite this