Graph expansion and the unique games conjecture
From MaRDI portal
Publication:2875199
DOI10.1145/1806689.1806792zbMATH Open1293.05373OpenAlexW2019404063WikidataQ61068278 ScholiaQ61068278MaRDI QIDQ2875199FDOQ2875199
Authors: Prasad Raghavendra, David Steurer 
Publication date: 13 August 2014
Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1806689.1806792
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
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)
Cited In (75)
- Title not available (Why is that?)
- Max-min greedy matching problem: hardness for the adversary and fractional variant
- Pseudorandom sets in Grassmann graph have near-perfect expansion
- Geometric bounds on the fastest mixing Markov chain
- Mathematics of computation through the lens of linear equations and lattices
- 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
- Max-min greedy matching problem: hardness for the adversary and fractional variant
- Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms
- Finding connected \(k\)-subgraphs with high density
- Low rank approximation in the presence of outliers
- 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
- On the proof of the 2-to-2 games conjecture
- A note on the set union knapsack problem
- 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
- Parallel repetition of two-prover one-round games: an exposition
- Approximation algorithms and hardness of the \(k\)-route cut problem
- Log-Sobolev inequality for the multislice, with applications
- On non-optimally expanding sets in Grassmann graphs
- Multiwinner analogues of the plurality rule: axiomatic and algorithmic perspectives
- 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
- Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
- The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\)
- Gap amplification for small-set expansion via random walks
- Title not available (Why is that?)
- Tight inapproximability of minimum maximal matching on bipartite graphs and related problems
- Title not available (Why is that?)
- Election control through social influence with unknown preferences
- Approximation algorithms for finding maximum induced expanders
- The small set vertex expansion problem
- Expander spanning subgraphs with large girth
- Finding Connected Dense $$k$$-Subgraphs
- Computing Tree Decompositions
- Title not available (Why is that?)
- 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
- Approximation Algorithms for CSPs
- Lower bounds for treewidth of product graphs
- Election control through social influence with voters' uncertainty
- Minimum fill-in: inapproximability and almost tight lower bounds
- Title not available (Why is that?)
- Finding a collective set of items: from proportional multirepresentation to group recommendation
- On non-optimally expanding sets in Grassmann graphs
- 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\)
- Dimension reduction for maximum matchings and the fastest mixing Markov chain
- 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
- 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
- Title not available (Why is that?)
- Sampling-based dimension reduction for subspace approximation with outliers
- Dimension-free L2 maximal inequality for spherical means in the hypercube
- Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time
- Unique games on the hypercube
- Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery
- Polynomial integrality gaps for strong SDP relaxations of densest \(k\)-subgraph
- 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
- Minimum congestion mapping in a cloud
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)
