Subexponential algorithms for unique games and related problems
From MaRDI portal
Publication:3177749
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)
Recommendations
Cited in
(52)- Crux, space constraints and subdivisions
- Towards the Erdős-Gallai cycle decomposition conjecture
- On the hardest problem formulations for the 0/1 Lasserre hierarchy
- Spectral algorithms for unique games
- On Khot’s unique games conjecture
- Finding and using expanders in locally sparse graphs
- Approximately counting independent sets in bipartite graphs via graph containers
- Computational topology and the unique games conjecture
- A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies
- Hypercontractivity, sum-of-squares proofs, and their applications
- Making the Long Code Shorter
- New NP-hardness results for 3-coloring and 2-to-1 label cover
- scientific article; zbMATH DE number 7053310 (Why is no real title available?)
- Algorithmic extensions of Cheeger's inequality to higher eigenvalues and partitions
- Approximating unique games using low diameter graph decomposition
- Quantum de Finetti theorems under local measurements with applications
- Graph and string parameters: connections between pathwidth, cutwidth and the locality number
- Approximation algorithms for finding maximum induced expanders
- Algorithms approaching the threshold for semi-random planted clique
- Maximum length-constrained flows and disjoint paths: distributed, deterministic, and fast
- Finding Pseudorandom Colorings of Pseudorandom Graphs
- A randomized subexponential algorithm for parity games
- Bi-covering: covering edges with two small subsets of vertices
- Local and global expansion in random geometric graphs
- Bipartite communities via spectral partitioning
- Efficient algorithms for the Potts model on small-set expanders
- Domination chain: characterisation, classical complexity, parameterised complexity and approximability
- Random walks and forbidden minors. I: An \(n^{1/2+o(1)}\)-query one-sided tester for minor closed properties on bounded degree graphs
- U-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
- New tools for graph coloring
- Graph expansion and the unique games conjecture
- On a connection between small set expansions and modularity clustering
- Mathematics of computation through the lens of linear equations and lattices
- 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
- Designing FPT algorithms for cut problems using randomized contractions
- Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms
- Why are CSPs based on partition schemes computationally hard?
- Combinatorial structure and randomized subexponential algorithms for infinite games
- The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into \(\ell_1\)
- The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\)
- \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
- Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem
- Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
- Pseudorandom sets in Grassmann graph have near-perfect expansion
- Improved approximation algorithms for projection games
- On the hardest problem formulations for the \(0/1\) Lasserre hierarchy
- Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials
- 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!
- Improved Cheeger's inequality and analysis of local graph partitioning using vertex expansion and expansion profile
- Sum of squares lower bounds from symmetry and a good story
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)
