Volume 21, issue 3 (2021)

Download this article
Download this article For screen
For printing
Recent Issues

Volume 23
Issue 9, 3909–4400
Issue 8, 3417–3908
Issue 7, 2925–3415
Issue 6, 2415–2924
Issue 5, 1935–2414
Issue 4, 1463–1934
Issue 3, 963–1462
Issue 2, 509–962
Issue 1, 1–508

Volume 22, 8 issues

Volume 21, 7 issues

Volume 20, 7 issues

Volume 19, 7 issues

Volume 18, 7 issues

Volume 17, 6 issues

Volume 16, 6 issues

Volume 15, 6 issues

Volume 14, 6 issues

Volume 13, 6 issues

Volume 12, 4 issues

Volume 11, 5 issues

Volume 10, 4 issues

Volume 9, 4 issues

Volume 8, 4 issues

Volume 7, 4 issues

Volume 6, 5 issues

Volume 5, 4 issues

Volume 4, 2 issues

Volume 3, 2 issues

Volume 2, 2 issues

Volume 1, 2 issues

The Journal
About the Journal
Editorial Board
Editorial Interests
Subscriptions
 
Submission Guidelines
Submission Page
Policies for Authors
Ethics Statement
 
ISSN (electronic): 1472-2739
ISSN (print): 1472-2747
Author Index
To Appear
 
Other MSP Journals
Coloring invariants of knots and links are often intractable

Greg Kuperberg and Eric Samperton

Algebraic & Geometric Topology 21 (2021) 1479–1510
Bibliography
1 S Aaronson, C Granade, G Kuperberg, V Russo, The complexity zoo, electronic resource
2 I Agol, J Hass, W Thurston, The computational complexity of knot genus and spanning area, Trans. Amer. Math. Soc. 358 (2006) 3821 MR2219001
3 S Arora, B Barak, Computational complexity: a modern approach, Cambridge Univ. Press (2009) MR2500087
4 R Barbanchon, On unique graph 3–colorability and parsimonious reductions in the plane, Theoret. Comput. Sci. 319 (2004) 455 MR2074967
5 C H Bennett, E Bernstein, G Brassard, U Vazirani, Strengths and weaknesses of quantum computing, SIAM J. Comput. 26 (1997) 1510 MR1471991
6 H L Bodlaender, A partial k–arboretum of graphs with bounded treewidth, Theoret. Comput. Sci. 209 (1998) 1 MR1647486
7 M Bordewich, M Freedman, L Lovász, D Welsh, Approximate counting and quantum computation, Combin. Probab. Comput. 14 (2005) 737 MR2174653
8 N Brand, Classifying spaces for branched coverings, Indiana Univ. Math. J. 29 (1980) 229 MR563208
9 J Y Cai, A Pavan, D Sivakumar, On the hardness of permanent, from: "STACS 99" (editors C Meinel, S Tison), Lect. Notes Comput. Sci. 1563, Springer (1999) 90 MR1734039
10 R H Crowell, R H Fox, Introduction to knot theory, Ginn (1963) MR0146828
11 J D Dixon, B Mortimer, Permutation groups, 163, Springer (1996) MR1409812
12 N M Dunfield, W P Thurston, Finite covers of random 3–manifolds, Invent. Math. 166 (2006) 457 MR2257389
13 J S Ellenberg, A Venkatesh, C Westerland, Homological stability for Hurwitz spaces and the Cohen–Lenstra conjecture over function fields, II, preprint (2012) arXiv:1212.0923v1
14 C Even-Zohar, Models of random knots, J. Appl. Comput. Topol. 1 (2017) 263 MR3975555
15 R H Fox, A quick trip through knot theory, from: "Topology of 3–manifolds and related topics" (editor M K Fort), Prentice-Hall (1962) 120 MR0140099
16 M D Fried, H Völklein, The inverse Galois problem and rational points on moduli spaces, Math. Ann. 290 (1991) 771 MR1119950
17 R Gilman, Finite quotients of the automorphism group of a free group, Canadian J. Math. 29 (1977) 541 MR435226
18 E Goursat, Sur les substitutions orthogonales et les divisions régulières de l’espace, Ann. Sci. École Norm. Sup. 6 (1889) 9 MR1508819
19 P Hall, The Eulerian functions of a group, Q. J. Math. 7 (1936) 134
20 P de la Harpe, V F R Jones, Graph invariants related to statistical mechanical models: examples and problems, J. Combin. Theory Ser. B 57 (1993) 207 MR1207488
21 R Impagliazzo, R Paturi, On the complexity of k–SAT, J. Comput. System Sci. 62 (2001) 367 MR1820597
22 F Jaeger, Tutte polynomials and link polynomials, Proc. Amer. Math. Soc. 103 (1988) 647 MR943099
23 F Jaeger, D L Vertigan, D J A Welsh, On the computational complexity of the Jones and Tutte polynomials, Math. Proc. Cambridge Philos. Soc. 108 (1990) 35 MR1049758
24 M Jerrum, A Sinclair, E Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, J. ACM 51 (2004) 671 MR2147852
25 D Koenig, A Tsvietkova, NP-hard problems naturally arising in knot theory, preprint (2018) arXiv:1809.10334
26 H Krovi, A Russell, Quantum Fourier transforms and the complexity of link invariants for quantum doubles of finite groups, Comm. Math. Phys. 334 (2015) 743 MR3306603
27 G Kuperberg, How hard is it to approximate the Jones polynomial ?, Theory Comput. 11 (2015) 183 MR3354608
28 G Kuperberg, E Samperton, Computational complexity and 3–manifolds and zombies, Geom. Topol. 22 (2018) 3623 MR3858771
29 M Lackenby, Some conditionally hard problems on links and 3–manifolds, Discrete Comput. Geom. 58 (2017) 580 MR3690662
30 R J Lipton, R E Tarjan, A separator theorem for planar graphs, SIAM J. Appl. Math. 36 (1979) 177 MR524495
31 D Lokshtanov, D Marx, S Saurabh, Lower bounds based on the exponential time hypothesis, Bull. Eur. Assoc. Theor. Comput. Sci. 105 (2011) 41 MR2917970
32 A de Mesmay, Y Rieck, E Sedgwick, M Tancer, The unbearable hardness of unknotting, from: "35th International Symposium on Computational Geometry" (editors G Barequet, Y Wang), Leibniz Int. Proc. Inform. 129, Schloss Dagstuhl. Leibniz-Zent. Inform. (2019) MR3968635
33 J Munkres, Algorithms for the assignment and transportation problems, J. Soc. Indust. Appl. Math. 5 (1957) 32 MR93429
34 K Reidemeister, Knoten und Gruppen, Abh. Math. Sem. Univ. Hamburg 5 (1927) 7 MR3069461
35 K A Ribet, On l–adic representations attached to modular forms, Invent. Math. 28 (1975) 245 MR419358
36 K A Ribet, Galois action on division points of abelian varieties with real multiplications, Amer. J. Math. 98 (1976) 751 MR457455
37 D P Roberts, A Venkatesh, Hurwitz monodromy and full number fields, Algebra Number Theory 9 (2015) 511 MR3340543
38 E Samperton, Schur-type invariants of branched G–covers of surfaces, from: "Topological phases of matter and quantum computation" (editors P Bruillard, C Ortiz Marrero, J Plavnik), Contemp. Math. 747, Amer. Math. Soc. (2020) 173 MR4079751
39 L G Valiant, The complexity of computing the permanent, Theoret. Comput. Sci. 8 (1979) 189 MR526203
40 L G Valiant, V V Vazirani, NP is as easy as detecting unique solutions, Theoret. Comput. Sci. 47 (1986) 85 MR871466