publication . Other literature type . Preprint . 2018 . Embargo end date: 24 May 2018

Computational Topology and the Unique Games Conjecture

Grochow, Joshua A.; Tucker-Foltz, Jamie;
Open Access English
  • Published: 19 Mar 2018
  • Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany
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 ...
Read more
doi: 10.4230/lipics.socg.2018.43
Subjects
arXiv: Computer Science::Computer Science and Game Theory
free text keywords: Computer Science, 000 Computer science, knowledge, general works, Computer Science - Computational Complexity, Computer Science - Computational Geometry, Computer Science - Discrete Mathematics, Mathematics - Algebraic Topology, 68Q25, 52C45, 68U05, 57M10, 68W25, 05C10, F.2.2
Related Organizations
Funded by
NSF| Collaborative Research: New Algorithms for Group Isomorphism
Project
Collaborative Research: New Algorithms for Group Isomorphism
  • Funder: National Science Foundation (NSF)
  • Project Code: 1750319
  • Funding stream: Directorate for Mathematical & Physical Sciences | Division of Mathematical Sciences
Download fromView all 2 versions
arXiv.org e-Print Archive
Preprint . 2018
Provider: arXiv.org e-Print Archive
http://dx.doi.org/10.4230/lipi...
Other literature type . 2018
Provider: Datacite
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany
42 references, page 1 of 3

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.

doi:10.1145/2775105.

[ACKM16] Naman Agarwal, Karthekeyan Chandrasekaran, Alexandra Kolla, and Vivek Madan. On the expansion of group-based lifts. arXiv:1311.3268 [cs.DM], 2016.

[ACKM17] 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. doi:10.4230/LIPIcs.APPROX-RANDOM.2017.24. [OpenAIRE]

Gunnar Andersson, Lars Engebretsen, and Johan Hastad. A new way of using semide nite programming with applications to linear equations mod p. J. Algorithms, 39(2):162{204, 2001.

Originally appeared in SODA 1999. doi:10.1006/jagm.2000.1154.

[AKK+08] 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 STOC '08: 40th Annual ACM Symposium on Theory of Computing, pages 21{28, 2008. doi:10.1145/1374376.1374380.

[AKKT15] Naman Agarwal, Guy Kindler, Alexandra Kolla, and Luca Trevisan. Unique games on the hypercube. Chic. J. Theoret. Comput. Sci., pages Article 1, 20, 2015. doi:10.4086/cjtcs. 2015.001.

Yonatan Bilu and Nathan Linial. Lifts, discrepancy and nearly optimal spectral gap. Combinatorica, 26(5):495{519, 2006. doi:10.1007/s00493-006-0029-7. [OpenAIRE]

Lawrence Breen. Notes on 1- and 2-gerbes. arXiv:math/0611317 [math.CT], 2006.

Toby Bartels and Urs Schreiber. Gerbe (in nonabelian cohomology). https://ncatlab.org/ nlab/show/gerbe+%28in+nonabelian+cohomology%29, 2009.

Erin W. Chambers, Je 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. doi:10.1145/1542362.1542426.

Comput., 41(6):1605{1634, 2012. Originally appeared in STOC 2009. doi:10.1137/090766863.

arXiv:07092512 [cs.CG], 2007.

Joshua A. Grochow and Jamie Tucker-Foltz. Computational topology and the unique games conjecture. In 34th International Symposium on Computational Geometry, SoCG 2018, pages 43:1{43:16, 2018. doi:10.4230/LIPIcs.SoCG.2018.43. [OpenAIRE]

42 references, page 1 of 3
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue