On Khot’s unique games conjecture
From MaRDI portal
Publication:3109809
DOI10.1090/S0273-0979-2011-01361-1zbMATH Open1280.68102WikidataQ122930890 ScholiaQ122930890MaRDI QIDQ3109809FDOQ3109809
Authors: Luca Trevisan 
Publication date: 26 January 2012
Published in: Bulletin of the American Mathematical Society (Search for Journal in Brave)
Recommendations
- Graph expansion and the unique games conjecture
- Approximation algorithms for unique games
- A new point of NP-hardness for unique games
- An approach to solution uniqueness in game problems
- Computational topology and the unique games conjecture
- Yet another step toward the uniqueness of solutions of game problems
- Yet another step toward the uniqueness of solutions of game problems
- Near-optimal algorithms for unique games
- Proof of a conjecture on game domination
- Approximating unique games using low diameter graph decomposition
Semidefinite programming (90C22) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Eigenvalues and expanders
- Computational Complexity
- Proof verification and the hardness of approximation problems
- Gadgets, Approximation, and Linear Programming
- A $(\log n)^{\Omega(1)}$ Integrality Gap for the Sparsest Cut SDP
- Applications of approximation algorithms to cooperative games
- Some optimal inapproximability results
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Laplacian eigenvalues and the maximum cut problem
- Title not available (Why is that?)
- On the power of unique 2-prover 1-round games
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Noise stability of functions with low influences: invariance and optimality
- Title not available (Why is that?)
- Limit theorems for polylinear forms
- Euclidean distortion and the sparsest cut (extended abstract)
- Expander flows, geometric embeddings and graph partitioning
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- Geometric bounds on the Ornstein-Uhlenbeck velocity process
- A Parallel Repetition Theorem
- Efficient probabilistically checkable proofs and applications to approximations
- On weighted vs unweighted versions of combinatorial optimization problems
- Improved lower bounds for embeddings into \(L_1\)
- Title not available (Why is that?)
- Combinatorial properties and the complexity of a max-cut approximation
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Subexponential algorithms for unique games and related problems
- On the optimality of the random hyperplane rounding technique for MAX CUT
- The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into \(\ell_1\)
- Near-optimal algorithms for unique games
- Integrality gaps for sparsest cut and minimum linear arrangement problems
Cited In (15)
- Synchronicity for quantum non-local games
- Why did the shape of your network change? (On detecting network anomalies via non-local curvatures)
- Limitations of semidefinite programs for separable states and entangled games
- Hardness of approximation
- A periodic isoperimetric problem related to the unique games conjecture
- The work of Subhash Khot
- Vertical perimeter versus horizontal perimeter
- Pseudorandom sets in Grassmann graph have near-perfect expansion
- On optimal approximability results for computing the strong metric dimension
- On computational capabilities of Ising machines based on nonlinear oscillators
- Scheduling results applicable to decision-theoretic troubleshooting
- Can we resolve the continuum hypothesis?
- On \(L_1\)-embeddability of unions of \(L_1\)-embeddable metric spaces and of twisted unions of hypercubes
- On Flattenability of Graphs
- Truth vs. proof in computational complexity
This page was built for publication: On Khot’s unique games conjecture
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3109809)
