scientific article; zbMATH DE number 6471447

DOI10.4086/cjtcs.2015.001zbMath1336.68092arXiv1405.1374OpenAlexW4230972002MaRDI QIDQ5500595

Guy Kindler, Naman Agarwal, Alexandra Kolla, Luca Trevisan

Publication date: 7 August 2015

Published in: Chicago Journal of Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1405.1374

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

hypercubesemi-definite programmingintegrality gapunique games

Mathematics Subject Classification ID

Semidefinite programming (90C22) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (2)

Approximating Unique Games Using Low Diameter Graph Decomposition ⋮ Computational topology and the Unique Games Conjecture

Cites Work

• Unnamed Item
• Graph expansion and the unique games conjecture
• On the power of unique 2-prover 1-round games
• How Good is the Goemans--Williamson MAX CUT Algorithm?
• On the optimality of the random hyperplane rounding technique for MAX CUT
• Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES

This page was built for publication: