Algebraic & Geometric Topology Volume 21, issue 3 (2021)

Download this article
	For screen
	For printing

Recent 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

DOI: 10.2140/agt.2021.21.1479

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