Near-optimal algorithms for unique games
From MaRDI portal
Publication:2931385
DOI10.1145/1132516.1132547zbMATH Open1301.68267OpenAlexW2165732281MaRDI QIDQ2931385FDOQ2931385
Authors: Konstantin Makarychev, Yury Makarychev, Moses Charikar 
Publication date: 25 November 2014
Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1132516.1132547
Recommendations
Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Approximation algorithms (68W25)
Cited In (48)
- Making the Long Code Shorter
- An improved heuristic for the ``Ulam-Rényi game
- Approximating maximum satisfiable subsystems of linear equations of bounded width
- Computational topology and the unique games conjecture
- Approximating unique games using low diameter graph decomposition
- Inapproximability of unique games in fixed-point logic with counting
- Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems
- Subexponential algorithms for unique games and related problems
- Column subset selection problem is UG-hard
- Lasserre integrality gaps for graph spanners and related problems
- Title not available (Why is that?)
- A note on unique games
- On Khot’s unique games conjecture
- Title not available (Why is that?)
- A new point of NP-hardness for unique games
- Linear index coding via semidefinite programming
- Fast SDP algorithms for constraint satisfaction problems
- Approximate Lasserre integrality gap for unique games
- Explicit optimal hardness via Gaussian stability results
- Approximation Algorithms for CSPs
- Re-optimization of constraint satisfaction problems with predicates of arity two
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Mathematics of computation through the lens of linear equations and lattices
- Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope
- Approximating CSPs using LP relaxation
- On unique games with negative weights
- Angular synchronization by eigenvectors and semidefinite programming
- Optimal constant-time approximation algorithms and (unconditional) inapproximability results for every bounded-degree CSP
- Sharp kernel clustering algorithms and their associated Grothendieck inequalities
- Spectral algorithms for unique games
- Approximate kernel clustering
- Hard constraint satisfaction problems have hard gaps at location 1
- Approximation algorithms for unique games
- Playing Games with Approximation Algorithms
- Large violation of Bell inequalities with low entanglement
- Improved Rounding for Parallel Repeated Unique Games
- Unique games on the hypercube
- Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem
- Title not available (Why is that?)
- Robust algorithms with polynomial loss for near-unanimity CSPs
- Contention resolution, matrix scaling and fair allocation
- Robustly solvable constraint satisfaction problems
- Sum-of-squares proofs and the quest toward optimal algorithms
- Unique games on expanding constraint graphs are easy (extended abstract)
- Candidate hard unique game
- Non-unique games over compact groups and orientation estimation in cryo-EM
This page was built for publication: Near-optimal algorithms for unique games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2931385)
