How to Play Unique Games on Expanders
From MaRDI portal
Publication:3075461
DOI10.1007/978-3-642-18318-8_17zbMath1314.68401arXiv0903.0367OpenAlexW1511070007MaRDI QIDQ3075461
Konstantin Makarychev, Yury Makarychev
Publication date: 15 February 2011
Published in: Approximation and Online Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0903.0367
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Games on graphs (graph-theoretic aspects) (05C57)
Related Items
Tilings of rectangles with T-tetrominoes ⋮ Approximately counting independent sets in bipartite graphs via graph containers ⋮ Approximation Algorithms for CSPs ⋮ Approximating Unique Games Using Low Diameter Graph Decomposition ⋮ Algorithms for #BIS-Hard Problems on Expander Graphs ⋮ Computational topology and the Unique Games Conjecture ⋮ Unnamed Item ⋮ List-Decoding with Double Samplers