Subexponential algorithms for unique games and related problems
DOI10.1145/2775105zbMATH Open1426.05159DBLPjournals/jacm/AroraBS15OpenAlexW2242403914WikidataQ57568009 ScholiaQ57568009MaRDI QIDQ3177749FDOQ3177749
Boaz Barak, Sanjeev Arora, David Steurer
Publication date: 2 August 2018
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2775105
Recommendations
spectral graph theorygraph partitioninggraph decompositionunique games conjecturesmall set expansionspectral algorithms
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Games on graphs (graph-theoretic aspects) (05C57) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cited In (49)
- Title not available (Why is that?)
- Making the Long Code Shorter
- Quantum de Finetti theorems under local measurements with applications
- Algorithmic Extensions of Cheeger’s Inequality to Higher Eigenvalues and Partitions
- Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
- On Khot’s unique games conjecture
- Title not available (Why is that?)
- Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms
- The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\)
- Partitioning Well-Clustered Graphs: Spectral Clustering Works!
- A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies
- Title not available (Why is that?)
- A randomized subexponential algorithm for parity games
- New Tools for Graph Coloring
- Designing FPT Algorithms for Cut Problems Using Randomized Contractions
- Finding Pseudorandom Colorings of Pseudorandom Graphs
- New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover
- The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1
- Pseudorandom sets in Grassmann graph have near-perfect expansion
- Local and global expansion in random geometric graphs
- Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile
- Bipartite communities via spectral partitioning
- Domination chain: characterisation, classical complexity, parameterised complexity and approximability
- Approximately counting independent sets in bipartite graphs via graph containers
- Multi-way spectral partitioning and higher-order cheeger inequalities
- Mathematics of computation through the lens of linear equations and lattices
- Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs
- Bi-Covering: Covering Edges with Two Small Subsets of Vertices
- Approximating Unique Games Using Low Diameter Graph Decomposition
- On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy
- Computational topology and the Unique Games Conjecture
- Crux, space constraints and subdivisions
- Towards the Erdős-Gallai cycle decomposition conjecture
- \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
- Spectral algorithms for unique games
- Algorithms approaching the threshold for semi-random planted clique
- Maximum length-constrained flows and disjoint paths: distributed, deterministic, and fast
- Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs
- On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy
- Title not available (Why is that?)
- Improved approximation algorithms for projection games
- Efficient algorithms for the Potts model on small-set expanders
- Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem
- Title not available (Why is that?)
- Effect of Gromov-hyperbolicity parameter on cuts and expansions in graphs and some algorithmic implications
- Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis
- Finding and Using Expanders in Locally Sparse Graphs
- Combinatorial structure and randomized subexponential algorithms for infinite games
- Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials
This page was built for publication: Subexponential algorithms for unique games and related problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177749)
