The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1

DOI10.1145/2629614zbMath1321.68316arXiv1305.4581OpenAlexW2619061098MaRDI QIDQ5501953

Subhash A. Khot, Nisheeth K. Vishnoi

Publication date: 14 August 2015

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1305.4581

zbMATH Keywords

semidefinite programminghardness of approximationintegrality gapunique games conjecturesparsest cutmetric embeddingsnegative-type metrics

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Lower bounds on lattice sieving and information set decoding, Vertical perimeter versus horizontal perimeter, Gaussian noise sensitivity and Fourier tails, A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time, Negative-type diversities, a multi-dimensional analogue of negative-type metrics, Bisection of bounded treewidth graphs by convolutions, On a class of metrics related to graph layout problems, Small bipartite subgraph polytopes, Mean isoperimetry with control on outliers: exact and approximation algorithms, Diversity-normed spaces and diversity embeddings, Linear‐time algorithms for eliminating claws in graphs, Pseudorandom sets in Grassmann graph have near-perfect expansion, Mathematics of computation through the lens of linear equations and lattices, Unnamed Item, Bi-Lipschitz embeddings of Heisenberg submanifolds into Euclidean spaces, Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis, Spectral algorithms for unique games, Unnamed Item, Minimum Bisection Is Fixed-Parameter Tractable, Random constructions in Bell inequalities: a survey, Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut, Vertex cover might be hard to approximate to within \(2 - \varepsilon \), Unnamed Item, Noise stability of functions with low influences: invariance and optimality, Differentiating maps into \(L^1\), and the geometry of BV functions, Survey on nonlocal games and operator space theory, Computational topology and the Unique Games Conjecture, Generalized differentiation and bi-Lipschitz nonembedding in \(L^{1}\), Quasimetric embeddings and their applications, Strong reductions for extended formulations, The Andoni–Krauthgamer–Razenshteyn Characterization of Sketchable Norms Fails for Sketchable Metrics, Expanders with respect to Hadamard spaces and random graphs, UG-hardness to NP-hardness by losing half, On Khot’s unique games conjecture, The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ ₁, Tight inapproximability of minimum maximal matching on bipartite graphs and related problems, On \(L_1\)-embeddability of unions of \(L_1\)-embeddable metric spaces and of twisted unions of hypercubes, Unnamed Item, Superlinear Integrality Gaps for the Minimum Majority Problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Differentiating maps into \(L^1\), and the geometry of BV functions
• The Euclidean distortion of the lamplighter group.
• On Lipschitz embedding of finite metric spaces in Hilbert space
• Semidefinite programming in combinatorial optimization
• On the distribution of the Fourier spectrum of Boolean functions
• The geometry of graphs and some of its algorithmic applications
• On the hardness of approximating Multicut and Sparsest-Cut
• Fréchet embeddings of negative type metrics
• Nonembeddability theorems via Fourier analysis
• On the nonexistence of uniform homeomorphisms between \(L^ p\)-spaces
• Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs
• Graph expansion and the unique games conjecture
• A better approximation ratio for the vertex cover problem
• Integrality gaps for sparsest cut and minimum linear arrangement problems
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Subexponential Algorithms for Unique Games and Related Problems
• Making the Long Code Shorter
• On the power of unique 2-prover 1-round games
• O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Improved Lower Bounds for Embeddings into $L_1$
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
• On the optimality of the random hyperplane rounding technique for MAX CUT
• Block bases of the Haar system as complemented subspaces of $L{\textunderscore }p$, $2<p<\infty $
• A $(\log n)^{\Omega(1)}$ Integrality Gap for the Sparsest Cut SDP
• SDP Integrality Gaps with Local ell_1-Embeddability
• Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES
• Lx = b
• A PRG for lipschitz functions of polynomials with applications to sparsest cut
• The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ ₁
• Expander flows, geometric embeddings and graph partitioning
• Geometry of cuts and metrics