Computational topology and the Unique Games Conjecture

Preprint English OPEN
Grochow, Joshua A.; Tucker-Foltz, Jamie;
(2018)
  • Related identifiers: doi: 10.4230/LIPIcs.SoCG.2018.43
  • Subject: 68Q25, 52C45, 68U05, 57M10, 68W25, 05C10 | Mathematics - Algebraic Topology | Computer Science - Computational Geometry | Computer Science - Discrete Mathematics | Computer Science - Computational Complexity | F.2.2
    arxiv: Computer Science::Computer Science and Game Theory
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 Ga... View more
  • References (42)
    42 references, page 1 of 5

    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.

    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.

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

  • Related Organizations (2)
  • Metrics
Share - Bookmark