×

Computational topology and the unique games conjecture. (English) Zbl 1489.68332

Speckmann, Bettina (ed.) et al., 34th international symposium on computational geometry, SoCG 2018, June 11–14, 2018, Budapest, Hungary. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 99, Article 43, 16 p. (2018).
Summary: 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 [S. Khot et al., SIAM J. Comput. 37, No. 1, 319–357 (2007; Zbl 1135.68019)] 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 C. Chen and D. Freedman [in: Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1594–1604 (2010; Zbl 1288.68088); Discrete Comput. Geom. 45, No. 3, 425–448 (2011; Zbl 1218.68084)] 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\), and we show Unique Games-completeness over \(\mathbb{Z}_k\) 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.
For the entire collection see [Zbl 1390.68027].

MSC:

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

References:

[1] Naman Agarwal, Karthekeyan Chandrasekaran, Alexandra Kolla, and Vivek Madan. On the expansion of group-based lifts. arXiv:1311.3268 [cs.DM], 2016. ##img## · Zbl 1470.05097
[2] Naman Agarwal, Karthekeyan Chandrasekaran, Alexandra Kolla, and Vivek Madan. On the expansion of group-based lifts. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2017, August 16-18, 2017, Berkeley, CA, USA, pages 24:1-24:13, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.24. · Zbl 1470.05097 · doi:10.4230/LIPIcs.APPROX-RANDOM.2017.24
[3] Naman Agarwal, Guy Kindler, Alexandra Kolla, and Luca Trevisan. Unique games on the hypercube. Chic. J. Theoret. Comput. Sci., pages Article 1, 20, 2015. URL: http://dx.doi.org/10.4086/cjtcs.2015.001. · Zbl 1336.68092 · doi:10.4086/cjtcs.2015.001
[4] Gunnar Andersson, Lars Engebretsen, and Johan Håstad. A new way of using semidefinite programming with applications to linear equations mod p. J. Algorithms, 39(2):162-204, 2001. Originally appeared in SODA 1999. URL: http://dx.doi.org/10.1006/jagm.2000.1154. · Zbl 1103.90385 · doi:10.1006/jagm.2000.1154
[5] Sanjeev Arora and Boaz Barak. Computational complexity. Cambridge University Press, Cambridge, 2009. A modern approach. URL: http://dx.doi.org/10.1017/CBO9780511804090. · Zbl 1193.68112 · doi:10.1017/CBO9780511804090
[6] Sanjeev Arora, Boaz Barak, and David Steurer. Subexponential algorithms for unique games and related problems. J. ACM, 62(5):Art. 42, 25, 2015. Originally appeared in FOCS 2010. URL: http://dx.doi.org/10.1145/2775105. · Zbl 1426.05159 · doi:10.1145/2775105
[7] Sanjeev Arora, Subhash A. Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani, and Nisheeth K. Vishnoi. Unique games on expanding constraint graphs are easy: Extended abstract. In \STOC0840th, pages 21-28, 2008. URL: http://dx.doi.org/10.1145/1374376.1374380. · Zbl 1231.68147 · doi:10.1145/1374376.1374380
[8] Yonatan Bilu and Nathan Linial. Lifts, discrepancy and nearly optimal spectral gap. Combinatorica, 26(5):495-519, 2006. URL: http://dx.doi.org/10.1007/s00493-006-0029-7. · Zbl 1121.05054 · doi:10.1007/s00493-006-0029-7
[9] Erin W. Chambers, Jeff Erickson, and Amir Nayyeri. Minimum cuts and shortest homologous cycles. In SoCG ’09: Proceedings of the 25th Annual Symposium on Computational Geometry, pages 377-385, 2009. URL: http://dx.doi.org/10.1145/1542362.1542426. · Zbl 1388.05177 · doi:10.1145/1542362.1542426
[10] Erin W. Chambers, Jeff Erickson, and Amir Nayyeri. Homology flows, cohomology cuts. SIAM J. Comput., 41(6):1605-1634, 2012. Originally appeared in STOC 2009. URL: http://dx.doi.org/10.1137/090766863. · Zbl 1260.05070 · doi:10.1137/090766863
[11] Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, and D. Sivakumar. On the hardness of approximating multicut and sparsest-cut. computational complexity, 15(2):94-114, Jun 2006. Originally appeared in CCC 2005. URL: http://dx.doi.org/10.1007/s00037-006-0210-9. · Zbl 1132.68418 · doi:10.1007/s00037-006-0210-9
[12] Chao Chen and Daniel Freedman. Quantifying homology classes II: Localization and stability. arXiv:07092512 [cs.CG], 2007. ##img##
[13] Chao Chen and Daniel Freedman. Measuring and computing natural generators for homology groups. Comput. Geom., 43(2):169-181, 2010. URL: http://dx.doi.org/10.1016/j.comgeo.2009.06.004. · Zbl 1203.65041 · doi:10.1016/j.comgeo.2009.06.004
[14] Chao Chen and Daniel Freedman. Hardness results for homology localization. Discrete Comput. Geom., 45(3):425-448, 2011. Originally appeared in SODA 2010. URL: http://dx.doi.org/10.1007/s00454-010-9322-8. · Zbl 1218.68084 · doi:10.1007/s00454-010-9322-8
[15] Tamal K. Dey, Anil N. Hirani, and Bala Krishnamoorthy. Optimal homologous cycles, total unimodularity, and linear programming. SIAM J. Comput., 40(4):1026-1044, 2011. Originally appeared in STOC 2010. URL: http://dx.doi.org/10.1137/100800245. · Zbl 1245.55010 · doi:10.1137/100800245
[16] Jeff Erickson and Amir Nayyeri. Minimum cuts and shortest non-separating cycles via homology covers. In SODA ’11: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1166-1176. SIAM, Philadelphia, PA, 2011. ##img## · Zbl 1376.05146
[17] Merrick L. Furst, Jonathan L. Gross, and Lyle A. McGeoch. Finding a maximum-genus graph imbedding. J. ACM, 35(3):523-534, 1988. URL: http://dx.doi.org/10.1145/44483.44485. · doi:10.1145/44483.44485
[18] Jonathan L. Gross and Thomas W. Tucker. Generating all graph coverings by permutation voltage assignments. Discrete Math., 18(3):273-283, 1977. URL: http://dx.doi.org/10.1016/0012-365X(77)90131-5. · Zbl 0375.55001 · doi:10.1016/0012-365X(77)90131-5
[19] Johan Håstad. Some optimal inapproximability results. J. ACM, 48(4):798-859, 2001. Originally appeared in STOC 1997. URL: http://dx.doi.org/10.1145/502090.502098. · Zbl 1127.68405 · doi:10.1145/502090.502098
[20] Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bull. Amer. Math. Soc. (N.S.), 43(4):439-561, 2006. URL: http://dx.doi.org/10.1090/S0273-0979-06-01126-8. · Zbl 1147.68608 · doi:10.1090/S0273-0979-06-01126-8
[21] Subhash Khot. On the power of unique 2-prover 1-round games. In \STOC0234th, pages 767-775. ACM, 2002. URL: http://dx.doi.org/10.1145/509907.510017. · Zbl 1192.68367 · doi:10.1145/509907.510017
[22] Subhash Khot. On the unique games conjecture (invited survey). In \CCC1025th, pages 99-121, June 2010. URL: http://dx.doi.org/10.1109/CCC.2010.19. · doi:10.1109/CCC.2010.19
[23] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput., 37(1):319-357, 2007. Originally appeared in FOCS 2004. URL: http://dx.doi.org/10.1137/S0097539705447372. · Zbl 1135.68019 · doi:10.1137/S0097539705447372
[24] Subhash Khot and Dana Moshkovitz. Candidate hard unique game. In \STOC1648th, pages 63-76, 2016. URL: http://dx.doi.org/10.1145/2897518.2897531. · Zbl 1373.68240 · doi:10.1145/2897518.2897531
[25] Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2-ε. J. Comput. System Sci., 74(3):335-349, 2008. Originally appeard in CCC 2003. URL: http://dx.doi.org/10.1016/j.jcss.2007.06.019. · Zbl 1133.68061 · doi:10.1016/j.jcss.2007.06.019
[26] Subhash A. Khot and Nisheeth K. Vishnoi. The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into 𝓁₁. J. ACM, 62(1):8:1-8:39, 2015. Originally appeared in FOCS 2005. URL: http://dx.doi.org/10.1145/2629614. · Zbl 1321.68316 · doi:10.1145/2629614
[27] Alexandra Kolla. Spectral algorithms for unique games. Comput. Complexity, 20(2):177-206, 2011. Originally appeared in CCC 2010. URL: http://dx.doi.org/10.1007/s00037-011-0011-7. · Zbl 1234.68120 · doi:10.1007/s00037-011-0011-7
[28] Martin W. Liebeck, E. A. O’Brien, Aner Shalev, and Pham Huu Tiep. The Ore conjecture. J. Eur. Math. Soc. (JEMS), 12(4):939-1008, 2010. URL: http://dx.doi.org/10.4171/JEMS/220. · Zbl 1205.20011 · doi:10.4171/JEMS/220
[29] Nati Linial. Lifts of graphs. Slides of presentation, available at http://www.cs.huji.ac.il/ nati/PAPERS/lifts_talk.pdf, 2005. URL: http://www.cs.huji.ac.il/ nati/PAPERS/lifts_talk.pdf
[30] Konstantin Makarychev and Yury Makarychev. How to play unique games on expanders. In Klaus Jansen and Roberto Solis-Oba, editors, Approximation and Online Algorithms: 8th International Workshop, WAOA 2010, Liverpool, UK, September 9-10, 2010. Revised Papers, pages 190-200, 2011. URL: http://dx.doi.org/10.1007/978-3-642-18318-8_17. · Zbl 1314.68401 · doi:10.1007/978-3-642-18318-8_17
[31] Adam W. Marcus, Daniel A. Spielman, and Nikhil Srivastava. Interlacing families I: Bipartite Ramanujan graphs of all degrees. Ann. of Math. (2), 182(1):307-325, 2015. URL: http://dx.doi.org/10.4007/annals.2015.182.1.7. · Zbl 1316.05066 · doi:10.4007/annals.2015.182.1.7
[32] Adam W. Marcus, Daniel A. Spielman, and Nikhil Srivastava. Interlacing families II: Mixed characteristic polynomials and the Kadison-Singer problem. Ann. of Math. (2), 182(1):327-350, 2015. URL: http://dx.doi.org/10.4007/annals.2015.182.1.8. · Zbl 1332.46056 · doi:10.4007/annals.2015.182.1.8
[33] Oystein Ore. Some remarks on commutators. Proc. Amer. Math. Soc., 2:307-314, 1951. URL: http://dx.doi.org/10.2307/2032506. · Zbl 0043.02402 · doi:10.2307/2032506
[34] Prasad Raghavendra. Optimal algorithms and inapproximability results for every CSP? In \STOC0840th, pages 245-254, 2008. URL: http://dx.doi.org/10.1145/1374376.1374414. · Zbl 1231.68142 · doi:10.1145/1374376.1374414
[35] Prasad Raghavendra and David Steurer. Graph expansion and the unique games conjecture. In \STOC1042nd, pages 755-764, 2010. URL: http://dx.doi.org/10.1145/1806689.1806792. · Zbl 1293.05373 · doi:10.1145/1806689.1806792
[36] Sartaj Sahni and Teofilo Gonzalez. P-complete approximation problems. J. ACM, 23(3):555-565, 1976. URL: http://dx.doi.org/10.1145/321958.321975. · Zbl 0348.90152 · doi:10.1145/321958.321975
[37] Vijay V. Vazirani. Approximation algorithms. Springer-Verlag, Berlin, 2001. ##img## · Zbl 1323.68570
[38] Nguyen Huy Xuong. How to determine the maximum genus of a graph. J. Combin. Theory Ser. B, 26(2):217-225, 1979. URL: http://dx.doi.org/10.1016/0095-8956(79)90058-3. · Zbl 0403.05035 · doi:10.1016/0095-8956(79)90058-3
[39] Afra Zomorodian and Gunnar Carlsson. Localized homology. Comput. Geom., 41(3):126-148, 2008. URL: http://dx.doi.org/10.1016/j.comgeo.2008.02.003. · Zbl 1155.65021 · doi:10.1016/j.comgeo.2008.02.003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.