On Khot’s unique games conjecture
From MaRDI portal
Publication:3109809
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
Cites work
- scientific article; zbMATH DE number 5595151 (Why is no real title available?)
- scientific article; zbMATH DE number 5485536 (Why is no real title available?)
- scientific article; zbMATH DE number 3489106 (Why is no real title available?)
- A $(\log n)^{\Omega(1)}$ Integrality Gap for the Sparsest Cut SDP
- A Parallel Repetition Theorem
- Applications of approximation algorithms to cooperative games
- Combinatorial properties and the complexity of a max-cut approximation
- Computational Complexity
- Efficient probabilistically checkable proofs and applications to approximations
- Eigenvalues and expanders
- Euclidean distortion and the sparsest cut (extended abstract)
- Expander flows, geometric embeddings and graph partitioning
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Gadgets, Approximation, and Linear Programming
- Geometric bounds on the Ornstein-Uhlenbeck velocity process
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Improved lower bounds for embeddings into \(L_1\)
- Integrality gaps for sparsest cut and minimum linear arrangement problems
- Laplacian eigenvalues and the maximum cut problem
- Limit theorems for polylinear forms
- Near-optimal algorithms for unique games
- Noise stability of functions with low influences: invariance and optimality
- On the optimality of the random hyperplane rounding technique for MAX CUT
- On the power of unique 2-prover 1-round games
- On weighted vs unweighted versions of combinatorial optimization problems
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Proof verification and the hardness of approximation problems
- Some optimal inapproximability results
- Subexponential algorithms for unique games and related problems
- The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into \(\ell_1\)
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
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
- On optimal approximability results for computing the strong metric dimension
- Pseudorandom sets in Grassmann graph have near-perfect expansion
- 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)
