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

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

doi:10.1007/978-3-642-14165-2_52

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

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

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings
Pages	617-628
Number of pages	12
Edition	PART 1
DOIs	https://doi.org/10.1007/978-3-642-14165-2_52
State	Published - 2010
Event	37th International Colloquium on Automata, Languages and Programming, ICALP 2010 - Bordeaux, France Duration: Jul 6 2010 → Jul 10 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 1
Volume	6198 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	37th International Colloquium on Automata, Languages and Programming, ICALP 2010
Country/Territory	France
City	Bordeaux
Period	7/6/10 → 7/10/10

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-14165-2_52

Cite this

Guruswami, V., Khot, S., O'Donnell, R., Popat, P., Tulsiani, M., & Wu, Y. (2010). SDP gaps for 2-to-1 and other label-cover variants. In Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings (PART 1 ed., pp. 617-628). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6198 LNCS, No. PART 1). https://doi.org/10.1007/978-3-642-14165-2_52

SDP gaps for 2-to-1 and other label-cover variants. / Guruswami, Venkatesan; Khot, Subhash; O'Donnell, Ryan et al.
Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings. PART 1. ed. 2010. p. 617-628 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6198 LNCS, No. PART 1).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Guruswami, V, Khot, S, O'Donnell, R, Popat, P, Tulsiani, M & Wu, Y 2010, SDP gaps for 2-to-1 and other label-cover variants. in Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings. PART 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 1, vol. 6198 LNCS, pp. 617-628, 37th International Colloquium on Automata, Languages and Programming, ICALP 2010, Bordeaux, France, 7/6/10. https://doi.org/10.1007/978-3-642-14165-2_52

Guruswami V, Khot S, O'Donnell R, Popat P, Tulsiani M, Wu Y. SDP gaps for 2-to-1 and other label-cover variants. In Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings. PART 1 ed. 2010. p. 617-628. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1). doi: 10.1007/978-3-642-14165-2_52

Guruswami, Venkatesan ; Khot, Subhash ; O'Donnell, Ryan et al. / SDP gaps for 2-to-1 and other label-cover variants. Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings. PART 1. ed. 2010. pp. 617-628 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1).

@inproceedings{4439abaa82be488cb3c280d4512530f8,

title = "SDP gaps for 2-to-1 and other label-cover variants",

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.",

author = "Venkatesan Guruswami and Subhash Khot and Ryan O'Donnell and Preyas Popat and Madhur Tulsiani and Yi Wu",

year = "2010",

doi = "10.1007/978-3-642-14165-2_52",

language = "English (US)",

isbn = "3642141641",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 1",

pages = "617--628",

booktitle = "Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings",

edition = "PART 1",

note = "37th International Colloquium on Automata, Languages and Programming, ICALP 2010 ; Conference date: 06-07-2010 Through 10-07-2010",

}

TY - GEN

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

AU - Guruswami, Venkatesan

AU - Khot, Subhash

AU - O'Donnell, Ryan

AU - Popat, Preyas

AU - Tulsiani, Madhur

AU - Wu, Yi

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=77955339829&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77955339829&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-14165-2_52

DO - 10.1007/978-3-642-14165-2_52

M3 - Conference contribution

AN - SCOPUS:77955339829

SN - 3642141641

SN - 9783642141645

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 617

EP - 628

BT - Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings

T2 - 37th International Colloquium on Automata, Languages and Programming, ICALP 2010

Y2 - 6 July 2010 through 10 July 2010

ER -

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

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this