Computational topology and the unique games conjecture

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

Authors: Joshua A. Grochow, Jamie Tucker-Foltz 

Publication date: 18 August 2020

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.

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

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

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)

Cites Work

• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem
• Computational Complexity
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Optimal homologous cycles, total unimodularity, and linear programming
• Expander graphs and their applications
• Applications of approximation algorithms to cooperative games
• Some optimal inapproximability results
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Some Remarks on Commutators
• Lifts, discrepancy and nearly optimal spectral gap
• The Ore conjecture.
• On the hardness of approximating Multicut and Sparsest-Cut
• Title not available (Why is that?)
• On the power of unique 2-prover 1-round games
• P-Complete Approximation Problems
• Generating all graph coverings by permutation voltage assignments
• How to determine the maximum genus of a graph
• Graph expansion and the unique games conjecture
• Localized homology
• Homology Flows, Cohomology Cuts
• Title not available (Why is that?)
• Minimum cuts and shortest homologous cycles
• Subexponential Algorithms for Unique Games and Related Problems
• How to Play Unique Games on Expanders
• The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into \(\ell_1\)
• Measuring and computing natural generators for homology groups
• Hardness results for homology localization
• Unique games on expanding constraint graphs are easy (extended abstract)
• Spectral algorithms for unique games
• A new way of using semidefinite programming with applications to linear equations mod \(p\)
• Candidate hard unique game
• On the Expansion of Group-Based Lifts
• Unique games on the hypercube

Cited In (3)

• Inapproximability of unique games in fixed-point logic with counting
• On Khot’s unique games conjecture
• 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)