SDP Gaps for 2-to-1 and Other Label-Cover Variants

DOI10.1007/978-3-642-14165-2_52zbMath1288.68092OpenAlexW1569176896MaRDI QIDQ3587413

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

Publication date: 7 September 2010

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-14165-2_52

Mathematics Subject Classification ID

Semidefinite programming (90C22) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover ⋮ Unnamed Item

This page was built for publication: SDP Gaps for 2-to-1 and Other Label-Cover Variants