Computational topology and the unique games conjecture

DOI10.4230/LIPICS.SOCG.2018.43zbMATH Open1489.68332MaRDI QIDQ5115811FDOQ5115811

Authors Joshua A. Grochow, Jamie Tucker-Foltz

Publication date 18 August 2020

Full work available at URL https://arxiv.org/abs/1803.06800

zbMATH Keywords

computational topologyinapproximabilityunique games conjecturecovering graphcellpermutation voltage graphhomology localizationgraph lift

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Relations of low-dimensional topology with graph theory (57M15) Covering spaces and low-dimensional topology (57M10) Computational aspects of digital topology (68U03)

Abstract: Covering spaces of graphs have long been useful for studying expanders (as "graph lifts") and unique games (as the "label-extended graph"). In this paper we advocate for the thesis that there is a much deeper relationship between computational topology and the Unique Games Conjecture. Our starting point is Linial's 2005 observation that the only known problems whose inapproximability is equivalent to the Unique Games Conjecture - Unique Games and Max-2Lin - are instances of Maximum Section of a Covering Space on graphs. We then observe that the reduction between these two problems (Khot-Kindler-Mossel-O'Donnell, FOCS 2004; SICOMP, 2007) gives a well-defined map of covering spaces. We further prove that inapproximability for Maximum Section of a Covering Space on (cell decompositions of) closed 2-manifolds is also equivalent to the Unique Games Conjecture. This gives the first new "Unique Games-complete" problem in over a decade. Our results partially settle an open question of Chen and Freedman (SODA 2010; Disc. Comput. Geom., 2011) from computational topology, by showing that their question is almost equivalent to the Unique Games Conjecture. (The main difference is that they ask for inapproximability over $mathbbZ/2mathbbZ$, and we show Unique Games-completeness over $mathbbZ/kmathbbZ$ for large $k$.) This equivalence comes from the fact that when the structure group $G$ of the covering space is Abelian - or more generally for principal $G$-bundles - Maximum Section of a $G$-Covering Space is the same as the well-studied problem of 1-Homology Localization. Although our most technically demanding result is an application of Unique Games to computational topology, we hope that our observations on the topological nature of the Unique Games Conjecture will lead to applications of algebraic topology to the Unique Games Conjecture in the future.

Recommendations

• On the proof of the 2-to-2 games conjecture
• Towards a proof of the 2-to-1 games conjecture?
• Graph expansion and the unique games conjecture
• scientific article; zbMATH DE number 91031
• Near-optimal algorithms for unique games

Cites work

• scientific article; zbMATH DE number 5485536 (Why is no real title available?)
• scientific article; zbMATH DE number 6783459 (Why is no real title available?)
• A new way of using semidefinite programming with applications to linear equations mod \(p\)
• Applications of approximation algorithms to cooperative games
• Candidate hard unique game
• Computational Complexity
• Expander graphs and their applications
• Generating all graph coverings by permutation voltage assignments
• Graph expansion and the unique games conjecture
• Hardness results for homology localization
• Homology Flows, Cohomology Cuts
• How to Play Unique Games on Expanders
• 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
• Lifts, discrepancy and nearly optimal spectral gap
• Localized homology
• Measuring and computing natural generators for homology groups
• Minimum cuts and shortest homologous cycles
• On the expansion of group-based lifts
• On the hardness of approximating Multicut and Sparsest-Cut
• On the power of unique 2-prover 1-round games
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• P-Complete Approximation Problems
• Some Remarks on Commutators
• Some optimal inapproximability results
• Spectral algorithms for unique games
• Subexponential algorithms for unique games and related problems
• The Ore conjecture.
• The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into \(\ell_1\)
• Unique games on expanding constraint graphs are easy (extended abstract)
• Unique games on the hypercube
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(3)

• On Khot’s unique games conjecture
• Inapproximability of unique games in fixed-point logic with counting
• Minimum Cuts in Surface Graphs

This page was built for publication: Computational topology and the unique games conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5115811)