Volume 21, issue 3 (2021)

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

Volume 25, 1 issue

Volume 24, 9 issues

Volume 23, 9 issues

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
Subscriptions
 
Submission Guidelines
Submission Page
Policies for Authors
Ethics Statement
 
ISSN 1472-2739 (online)
ISSN 1472-2747 (print)
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