Subexponential algorithms for unique games and related problems
DOI10.1145/2775105zbMATH Open1426.05159DBLPjournals/jacm/AroraBS15OpenAlexW2242403914WikidataQ57568009 ScholiaQ57568009MaRDI QIDQ3177749FDOQ3177749
Authors: Boaz Barak, David Steurer, Sanjeev Arora 
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 (55)
- Crux, space constraints and subdivisions
- Efficient algorithms for the Potts model on small-set expanders
- Title not available (Why is that?)
- Decomposing a graph into expanding subgraphs
- Making the Long Code Shorter
- Quantum de Finetti theorems under local measurements with applications
- Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
- Computational topology and the unique games conjecture
- Approximating unique games using low diameter graph decomposition
- New tools for graph coloring
- Designing FPT algorithms for cut problems using randomized contractions
- Bi-covering: covering edges with two small subsets of vertices
- New NP-hardness results for 3-coloring and 2-to-1 label cover
- Graph expansion and the unique games conjecture
- On Khot’s unique games conjecture
- Why are CSPs based on partition schemes computationally hard?
- 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}\)
- On the hardest problem formulations for the \(0/1\) Lasserre hierarchy
- Approximation algorithms for finding maximum induced expanders
- Title not available (Why is that?)
- A randomized subexponential algorithm for parity games
- Finding Pseudorandom Colorings of Pseudorandom Graphs
- Pseudorandom sets in Grassmann graph have near-perfect expansion
- Finding and using expanders in locally sparse graphs
- A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies
- Local and global expansion in random geometric graphs
- Random walks and forbidden minors. I: An \(n^{1/2+o(1)}\)-query one-sided tester for minor closed properties on bounded degree graphs
- Bipartite communities via spectral partitioning
- On a connection between small set expansions and modularity clustering
- Domination chain: characterisation, classical complexity, parameterised complexity and approximability
- On the hardest problem formulations for the 0/1 Lasserre hierarchy
- Approximately counting independent sets in bipartite graphs via graph containers
- 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
- Partitioning well-clustered graphs: spectral clustering works!
- U-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
- A new regularity lemma and faster approximation algorithms for low threshold rank graphs
- The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into \(\ell_1\)
- 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
- Algorithmic extensions of Cheeger's inequality to higher eigenvalues and partitions
- Algorithms approaching the threshold for semi-random planted clique
- Maximum length-constrained flows and disjoint paths: distributed, deterministic, and fast
- Multi-way spectral partitioning and higher-order Cheeger inequalities
- Improved approximation algorithms for projection games
- 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
- Improved Cheeger's inequality and analysis of local graph partitioning using vertex expansion and expansion profile
- Hypercontractivity, sum-of-squares proofs, and their applications
- 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)
