Computational topology and the Unique Games Conjecture
Computational topology and the Unique Games Conjecture
复制标题
计算拓扑和独特博弈猜想
DOI：
10.4230/lipics.socg.2018.43
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Jamie Tucker
中科院分区：
文献类型：
--
作者：
Joshua A. Grochow;Jamie Tucker
图的覆盖空间长期以来对于研究扩张器（如“图提升”）和唯一游戏（如“标签扩展图”）很有用。在本文中，我们主张的论文，有一个更深的关系之间的计算拓扑和唯一的游戏猜想。我们的起点是Linial 2005年的观察，即唯一已知的不可逼近性相当于唯一游戏猜想的问题--唯一游戏和Max-2 Lin--是图上覆盖空间最大截面的实例。然后，我们观察到这两个问题之间的约化（Khot-Kindler-Mossel-O 'Donnell，FOCS 2004; SICOMP，2007）给出了一个定义良好的覆盖空间映射。进一步证明了闭2-流形（胞腔分解）上覆盖空间最大截面的不可逼近性也等价于唯一对策猜想。这给出了十多年来第一个新的“独特游戏完整”问题。
我们的研究结果部分解决了Chen和Freedman的一个悬而未决的问题（SODA 2010; Disc. Comput. Geom.，2011）从计算拓扑学，通过表明他们的问题几乎等同于唯一博弈猜想。(The主要的区别是，它们要求在$\mathbb{Z}/2\mathbb{Z}$上的不可逼近性，我们证明了在$\mathbb{Z}/k\mathbb{Z}$上的唯一博弈完备性，对于大的k$。这种等价性来自于这样一个事实，即当覆盖空间的结构群G是阿贝尔的-或者更一般地对于主G-丛-G-覆盖空间的最大截面与研究得很好的1-同调局部化问题相同。
虽然我们最技术要求的结果是唯一游戏的应用计算拓扑，我们希望我们的观察独特的游戏猜想的拓扑性质将导致应用代数拓扑的唯一游戏猜想在未来。
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 $\mathbb{Z}/2\mathbb{Z}$, and we show Unique Games-completeness over $\mathbb{Z}/k\mathbb{Z}$ 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.
影响因子：
0.8
作者：
Agarwal, Naman;Chandrasekaran, Karthekeyan;Kolla, Alexandra;Madan, Vivek
通讯作者：
Madan, Vivek