Document Open Access Logo

Computational Topology and the Unique Games Conjecture

Authors Joshua A. Grochow, Jamie Tucker-Foltz

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2018.43.pdf
  • Filesize: 0.48 MB
  • 16 pages

Document Identifiers

Author Details

Joshua A. Grochow
Jamie Tucker-Foltz

Cite As Get BibTex

Joshua A. Grochow and Jamie Tucker-Foltz. Computational Topology and the Unique Games Conjecture. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SoCG.2018.43

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 '04; SICOMP '07) 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 Z_2, and we show Unique Games-completeness over 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.

Subject Classification

Keywords
  • Unique Games Conjecture
  • homology localization
  • inapproximability
  • computational topology
  • graph lift
  • covering graph
  • permutation voltage graph
  • cell

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Naman Agarwal, Karthekeyan Chandrasekaran, Alexandra Kolla, and Vivek Madan. On the expansion of group-based lifts. arXiv:1311.3268 [cs.DM], 2016. Google Scholar
  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.
  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.
  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.
  5. Sanjeev Arora and Boaz Barak. Computational complexity. Cambridge University Press, Cambridge, 2009. A modern approach. URL: http://dx.doi.org/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.
  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.
  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.
  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.
  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.
  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.
  12. Chao Chen and Daniel Freedman. Quantifying homology classes II: Localization and stability. arXiv:07092512 [cs.CG], 2007. Google Scholar
  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.
  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.
  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.
  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. Google Scholar
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  33. Oystein Ore. Some remarks on commutators. Proc. Amer. Math. Soc., 2:307-314, 1951. URL: http://dx.doi.org/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.
  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.
  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.
  37. Vijay V. Vazirani. Approximation algorithms. Springer-Verlag, Berlin, 2001. Google Scholar
  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.
  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.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact