Subexponential algorithms for unique games and related problems
From MaRDI portal
(Redirected from Publication:3177749)
Subexponential algorithms for unique games and related problems (scientific article; zbMATH DE number 6912557)
Subexponential algorithms for unique games and related problems (scientific article; zbMATH DE number 6912557)
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
(59)- Hypercontractivity, sum-of-squares proofs, and their applications
- Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials
- Quantum de Finetti theorems under local measurements with applications
- Making the Long Code Shorter
- 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
- Faster exponential-time approximation algorithms using approximate monotone local search
- 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
- Graph and string parameters: connections between pathwidth, cutwidth and the locality number
- A randomized subexponential algorithm for parity games
- scientific article; zbMATH DE number 7053310 (Why is no real title available?)
- Finding Pseudorandom Colorings of Pseudorandom Graphs
- Sum of squares lower bounds from symmetry and a good story
- Finding and using expanders in locally sparse graphs
- Pseudorandom sets in Grassmann graph have near-perfect expansion
- A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies
- Random walks and forbidden minors. I: An \(n^{1/2+o(1)}\)-query one-sided tester for minor closed properties on bounded degree graphs
- Local and global expansion in random geometric graphs
- On a connection between small set expansions and modularity clustering
- Bipartite communities via spectral partitioning
- Domination chain: characterisation, classical complexity, parameterised complexity and approximability
- Randomness efficient noise stability and generalized small bias sets
- Narrowing the \textsf{LOCAL-CONGEST} gaps in sparse networks via expander decompositions
- 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
- Partitioning well-clustered graphs: spectral clustering works!
- 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
- Solving unique games over globally hypercontractive graphs
- A sublinear time tester for max-cut on clusterable graphs
- A spectral approach to approximately counting independent sets in dense bipartite graphs
- The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into _1
- Crux, space constraints and subdivisions
- Spectral algorithms for unique games
- \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
- Towards the Erdős-Gallai cycle decomposition conjecture
- 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
- Improved approximation algorithms for projection games
- Approximate monotone local search for weighted problems
- Efficient algorithms for the Potts model on small-set expanders
- Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem
- 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
- Combinatorial structure and randomized subexponential algorithms for infinite games
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)
