Computational topology and the Unique Games Conjecture
From MaRDI portal
Publication:5115811
DOI10.4230/LIPIcs.SoCG.2018.43zbMath1489.68332arXiv1803.06800MaRDI QIDQ5115811
Jamie Tucker-Foltz, Joshua A. Grochow
Publication date: 18 August 2020
Full work available at URL: https://arxiv.org/abs/1803.06800
inapproximabilityunique games conjecturecomputational topologycovering graphcellpermutation voltage graphhomology localizationgraph lift
Covering spaces and low-dimensional topology (57M10) Relations of low-dimensional topology with graph theory (57M15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational aspects of digital topology (68U03)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Hardness results for homology localization
- Spectral algorithms for unique games
- Lifts, discrepancy and nearly optimal spectral gap
- Localized homology
- The Ore conjecture.
- Measuring and computing natural generators for homology groups
- Generating all graph coverings by permutation voltage assignments
- How to determine the maximum genus of a graph
- Interlacing families. I: Bipartite Ramanujan graphs of all degrees
- Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem
- On the hardness of approximating Multicut and Sparsest-Cut
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- A New Way of Using Semidefinite Programming with Applications to Linear Equations mod p
- Optimal homologous cycles, total unimodularity, and linear programming
- Graph expansion and the unique games conjecture
- How to Play Unique Games on Expanders
- Subexponential Algorithms for Unique Games and Related Problems
- Expander graphs and their applications
- On the power of unique 2-prover 1-round games
- P-Complete Approximation Problems
- Homology Flows, Cohomology Cuts
- On the Expansion of Group-Based Lifts
- Applications of approximation algorithms to cooperative games
- Computational Complexity
- Candidate hard unique game
- Minimum cuts and shortest homologous cycles
- Some optimal inapproximability results
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1
- Some Remarks on Commutators
