Graph expansion and the unique games conjecture
From MaRDI portal
Publication:2875199
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Recommendations
- Subexponential algorithms for unique games and related problems
- Approximation algorithms for hypergraph small set expansion and small set vertex expansion
- On the proof of the 2-to-2 games conjecture
- Testing small set expansion in general graphs
- Approximation algorithms for hypergraph small-set expansion and small-set vertex expansion
Cited in
(75)- Finding connected \(k\)-subgraphs with high density
- scientific article; zbMATH DE number 7559088 (Why is no real title available?)
- Low rank approximation in the presence of outliers
- Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
- Max-min greedy matching problem: hardness for the adversary and fractional variant
- Computational topology and the unique games conjecture
- Approximating unique games using low diameter graph decomposition
- A note on the set union knapsack problem
- On the proof of the 2-to-2 games conjecture
- Sherali-Adams integrality gaps matching the log-density threshold
- Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis
- Subexponential algorithms for unique games and related problems
- Log-Sobolev inequality for the multislice, with applications
- Parallel repetition of two-prover one-round games: an exposition
- Approximation algorithms and hardness of the \(k\)-route cut problem
- Multiwinner analogues of the plurality rule: axiomatic and algorithmic perspectives
- On non-optimally expanding sets in Grassmann graphs
- On Khot’s unique games conjecture
- Hypergraph \(k\)-cut in randomized polynomial time
- Approximation and hardness results for the max \(k\)-uncut problem
- Approximation and hardness results for the max \(k\)-uncut problem
- The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\)
- Gap amplification for small-set expansion via random walks
- Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
- Tight inapproximability of minimum maximal matching on bipartite graphs and related problems
- scientific article; zbMATH DE number 7758340 (Why is no real title available?)
- Election control through social influence with unknown preferences
- scientific article; zbMATH DE number 7625166 (Why is no real title available?)
- The small set vertex expansion problem
- Expander spanning subgraphs with large girth
- Approximation algorithms for finding maximum induced expanders
- Graph and string parameters: connections between pathwidth, cutwidth and the locality number
- Finding Connected Dense $$k$$-Subgraphs
- Computing Tree Decompositions
- Pseudorandom sets in Grassmann graph have near-perfect expansion
- scientific article; zbMATH DE number 7559077 (Why is no real title available?)
- Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph
- Distributed corruption detection in networks
- On a connection between small set expansions and modularity clustering
- Lower bounds for treewidth of product graphs
- Election control through social influence with voters' uncertainty
- Approximation Algorithms for CSPs
- Minimum fill-in: inapproximability and almost tight lower bounds
- Finding a collective set of items: from proportional multirepresentation to group recommendation
- On non-optimally expanding sets in Grassmann graphs
- Geometric bounds on the fastest mixing Markov chain
- Mathematics of computation through the lens of linear equations and lattices
- Finding Cheeger cuts in hypergraphs via heat equation
- Approximation algorithms for hypergraph small set expansion and small set vertex expansion
- Hardness of bipartite expansion
- On the complexity of fair house allocation
- The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into \(\ell_1\)
- Spectral algorithms for unique games
- On set expansion problems and the small set expansion conjecture
- Algorithmic extensions of Cheeger's inequality to higher eigenvalues and partitions
- Dimension reduction for maximum matchings and the fastest mixing Markov chain
- Maximum length-constrained flows and disjoint paths: distributed, deterministic, and fast
- Sum-of-squares lower bounds for densest \(k\)-subgraph
- The power of unentangled quantum proofs with non-negative amplitudes
- Approximation algorithms for hypergraph small-set expansion and small-set vertex expansion
- Polynomial-time data reduction for weighted problems beyond additive goal functions
- Approximating CSPs with global cardinality constraints using SDP hierarchies
- Sampling-based dimension reduction for subspace approximation with outliers
- Dimension-free L2 maximal inequality for spherical means in the hypercube
- Max-min greedy matching problem: hardness for the adversary and fractional variant
- Almost polynomial hardness of node-disjoint paths in grids
- Unique games on the hypercube
- Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time
- Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery
- 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
- Polynomial integrality gaps for strong SDP relaxations of densest \(k\)-subgraph
- Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms
- Minimum congestion mapping in a cloud
- Fast and deterministic approximations for \(k\)-cut
This page was built for publication: Graph expansion and the unique games conjecture
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2875199)
