Near-optimal algorithms for unique games
From MaRDI portal
Publication:2931385
Recommendations
Cited in
(48)- Non-unique games over compact groups and orientation estimation in cryo-EM
- Candidate hard unique game
- 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
- Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
- Inapproximability of unique games in fixed-point logic with counting
- 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
- Lasserre integrality gaps for graph spanners and related problems
- Column subset selection problem is UG-hard
- A note on unique games
- scientific article; zbMATH DE number 7650072 (Why is no real title available?)
- On Khot’s unique games conjecture
- scientific article; zbMATH DE number 7716602 (Why is no real title available?)
- 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
- Spectral algorithms for unique games
- Hard constraint satisfaction problems have hard gaps at location 1
- Sharp kernel clustering algorithms and their associated Grothendieck inequalities
- Approximate kernel clustering
- 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
- Contention resolution, matrix scaling and fair allocation
- Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem
- Robustly solvable constraint satisfaction problems
- scientific article; zbMATH DE number 7559121 (Why is no real title available?)
- Robust algorithms with polynomial loss for near-unanimity CSPs
- Sum-of-squares proofs and the quest toward optimal algorithms
- Unique games on expanding constraint graphs are easy (extended abstract)
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)
