Unique games on the hypercube

DOI10.4086/CJTCS.2015.001MaRDI QIDQ5500595zbMATH OpenOpenAlexFDO

Authors Naman Agarwal, Guy Kindler, Alexandra Kolla, Luca Trevisan

Publication date 7 August 2015

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

hypercubeintegrality gapsemi-definite programmingunique games

Mathematics Subject Classification ID

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

Recommendations

• Near-optimal algorithms for unique games
• Approximation algorithms for unique games
• Unique games on expanding constraint graphs are easy (extended abstract)
• Spectral algorithms for unique games
• A note on unique games

Cites work

• Graph expansion and the unique games conjecture
• How Good is the Goemans--Williamson MAX CUT Algorithm?
• scientific article; zbMATH DE number 5485536 (Why is no real title available?)
• Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES
• On the optimality of the random hyperplane rounding technique for MAX CUT
• On the power of unique 2-prover 1-round games

Cited in

(7)

• How to Play Unique Games on Expanders
• Unique games on expanding constraint graphs are easy (extended abstract)
• Approximating unique games using low diameter graph decomposition
• scientific article; zbMATH DE number 7379291 (Why is no real title available?)
• A periodic isoperimetric problem related to the unique games conjecture
• Computational topology and the unique games conjecture
• On unique games with negative weights

This page was built for publication: Unique games on the hypercube

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5500595)