Graph expansion and the unique games conjecture
From MaRDI portal
Publication:2875199
DOI10.1145/1806689.1806792zbMath1293.05373OpenAlexW2019404063WikidataQ61068278 ScholiaQ61068278MaRDI QIDQ2875199
David Steurer, Prasad Raghavendra
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
Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Log-Sobolev inequality for the multislice, with applications ⋮ Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms ⋮ Computing Tree Decompositions ⋮ Approximation and hardness results for the max \(k\)-uncut problem ⋮ Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis ⋮ Finding a collective set of items: from proportional multirepresentation to group recommendation ⋮ Finding Cheeger cuts in hypergraphs via heat equation ⋮ Election control through social influence with voters' uncertainty ⋮ Finding connected \(k\)-subgraphs with high density ⋮ Unnamed Item ⋮ Finding Connected Dense $$k$$-Subgraphs ⋮ Multiwinner analogues of the plurality rule: axiomatic and algorithmic perspectives ⋮ Pseudorandom sets in Grassmann graph have near-perfect expansion ⋮ Dimension reduction for maximum matchings and the fastest mixing Markov chain ⋮ Approximation and Hardness Results for the Max k-Uncut Problem ⋮ Max-min greedy matching problem: hardness for the adversary and fractional variant ⋮ Polynomial-time data reduction for weighted problems beyond additive goal functions ⋮ Expander spanning subgraphs with large girth ⋮ Geometric bounds on the fastest mixing Markov chain ⋮ Mathematics of computation through the lens of linear equations and lattices ⋮ Unnamed Item ⋮ Unnamed Item ⋮ 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 ⋮ Spectral algorithms for unique games ⋮ Unnamed Item ⋮ Parallel Repetition of Two-Prover One-Round Games: An Exposition ⋮ A note on the set union knapsack problem ⋮ Sampling-based dimension reduction for subspace approximation with outliers ⋮ Approximation Algorithms for CSPs ⋮ Hypergraph \(k\)-cut in randomized polynomial time ⋮ Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery ⋮ Approximating Unique Games Using Low Diameter Graph Decomposition ⋮ Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder ⋮ The Small Set Vertex expansion problem ⋮ On set expansion problems and the small set expansion conjecture ⋮ Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Multi-way spectral partitioning and higher-order cheeger inequalities ⋮ Unnamed Item ⋮ The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\) ⋮ Election control through social influence with unknown preferences ⋮ Computational topology and the Unique Games Conjecture ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Dimension-free L2 maximal inequality for spherical means in the hypercube ⋮ Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph ⋮ Lower bounds for treewidth of product graphs ⋮ Distributed Corruption Detection in Networks ⋮ Minimum fill-in: inapproximability and almost tight lower bounds ⋮ Algorithmic Extensions of Cheeger’s Inequality to Higher Eigenvalues and Partitions ⋮ On the complexity of fair house allocation ⋮ The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1 ⋮ Tight inapproximability of minimum maximal matching on bipartite graphs and related problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Minimum Congestion Mapping in a Cloud ⋮ Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time
