Geometry & Topology Volume 22, issue 6 (2018)

Download this article
	For screen
	For printing

Recent Issues

The Journal

Submission Guidelines

Submission Page

Policies for Authors

Ethics Statement

ISSN 1364-0380 (online)

ISSN 1465-3060 (print)

Author Index

To Appear

Other MSP Journals

Computational complexity and $3$–manifolds and zombies

Greg Kuperberg and Eric Samperton

Geometry & Topology 22 (2018) 3623–3670

DOI: 10.2140/gt.2018.22.3623

Bibliography

1	S Aaronson, C Granade, G Kuperberg, V Russo, The complexity zoo, electronic resource
2	D Aharonov, I Arad, The BQP-hardness of approximating the Jones polynomial, preprint (2000) arXiv:quant-ph/0605181
3	G Alagic, C Lo, Quantum invariants of 3–manifolds and NP vs #P, preprint (2014) arXiv:1411.6049
4	S Arora, B Barak, Computational complexity: a modern approach, Cambridge Univ. Press (2009) MR2500087
5	M Aschenbrenner, S Friedl, H Wilton, Decision problems for 3–manifolds and their fundamental groups, from: "Interactions between low-dimensional topology and mapping class groups" (editors R I Baykur, J Etnyre, U Hamenstädt), Geom. Topol. Monogr. 19, Geom. Topol. Publ. (2015) 201 MR3609909
6	R Barbanchon, On unique graph 3–colorability and parsimonious reductions in the plane, Theoret. Comput. Sci. 319 (2004) 455 MR2074967
7	H Bass, M Lazard, J P Serre, Sous-groupes d’indice fini dans SL(n,Z), Bull. Amer. Math. Soc. 70 (1964) 385 MR0161913
8	K Bauer, D Sen, P Zvengrowski, A generalized Goursat lemma, Tatra Mt. Math. Publ. 64 (2015) 1 MR3458781
9	R W Carter, Simple groups of Lie type, 28, Wiley (1972) MR0407163
10	H Chen, Applying TQFT to count regular coverings of Seifert 3–manifolds, J. Geom. Phys. 62 (2012) 1347 MR2911210
11	P Diaconis, R L Graham, W M a Kantor, The mathematics of perfect shuffles, Adv. in Appl. Math. 4 (1983) 175 MR700845
12	R Dijkgraaf, E Witten, Topological gauge theories and group cohomology, Comm. Math. Phys. 129 (1990) 393 MR1048699
13	B R Donald, D R Chang, On the complexity of computing the homology type of a triangulation, from: "32nd Annual Symposium on Foundations of Computer Science", IEEE (1991) 650 MR1177213
14	N M Dunfield, W P Thurston, Finite covers of random 3–manifolds, Invent. Math. 166 (2006) 457 MR2257389
15	B Farb, D Margalit, A primer on mapping class groups, 49, Princeton Univ. Press (2012) MR2850125
16	E Fredkin, T Toffoli, Conservative logic, Internat. J. Theoret. Phys. 21 (1982) 219 MR657156
17	D S Freed, F Quinn, Chern–Simons theory with finite gauge group, Comm. Math. Phys. 156 (1993) 435 MR1240583
18	M H Freedman, M Larsen, Z Wang, A modular functor which is universal for quantum computation, Comm. Math. Phys. 227 (2002) 605 MR1910833
19	M H Freedman, M J Larsen, Z Wang, The two-eigenvalue problem and density of Jones representation of braid groups, Comm. Math. Phys. 228 (2002) 177 MR1911253
20	G Frobenius, I Schur, Über die reellen Darstellungen der endlichen Gruppen, Sitzungsber. Königlich Preussischen Akad. Wiss. 8 (1906) 186
21	M Goldmann, A Russell, The complexity of solving equations over finite groups, Inform. and Comput. 178 (2002) 253 MR1931744
22	E Goursat, Sur les substitutions orthogonales et les divisions régulières de l’espace, Ann. Sci. École Norm. Sup. 6 (1889) 9 MR1508819
23	P Hall, The Eulerian functions of a group, Quart. J. Math. 7 (1936) 134
24	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
25	D Johnson, The structure of the Torelli group, I : A finite set of generators for ℐ, Ann. of Math. 118 (1983) 423 MR727699
26	R Kannan, A Bachem, Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix, SIAM J. Comput. 8 (1979) 499 MR573842
27	R Koenig, G Kuperberg, B W Reichardt, Quantum computation with Turaev–Viro codes, Ann. Physics 325 (2010) 2707 MR2726654
28	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
29	G Kuperberg, Involutory Hopf algebras and 3–manifold invariants, Internat. J. Math. 2 (1991) 41 MR1082836
30	G Kuperberg, Denseness and Zariski denseness of Jones braid representations, Geom. Topol. 15 (2011) 11 MR2764112
31	G Kuperberg, Algorithmic homeomorphism of 3–manifolds as a corollary of geometrization, preprint (2015) arXiv:1508.06720
32	G Kuperberg, How hard is it to approximate the Jones polynomial ?, Theory Comput. 11 (2015) 183 MR3354608
33	G Kuperberg, E Samperton, Coloring invariants of knots and links are often intractable, in preparation
34	W B R Lickorish, An introduction to knot theory, 175, Springer (1997) MR1472978
35	J Maher, Random Heegaard splittings, J. Topol. 3 (2010) 997 MR2746344
36	G A Margulis, Discrete subgroups of semisimple Lie groups, 17, Springer (1991) MR1090825
37	A D Mednykh, Determination of the number of nonequivalent coverings over a compact Riemann surface, Dokl. Akad. Nauk SSSR 239 (1978) 269 MR490616
38	J Mennicke, Zur Theorie der Siegelschen Modulgruppe, Math. Ann. 159 (1965) 115 MR0181676
39	C Mochon, Anyons from non-solvable finite groups are sufficient for universal quantum computation, preprint (2000) arXiv:quant-ph/0206128
40	B H Neumann, Some remarks on infinite groups, J. London Math. Soc. 12 (1937) 120
41	G Nordh, P Jonsson, The complexity of counting solutions to systems of equations over finite semigroups, from: "Computing and combinatorics" (editors K Y Chwa, J I Munro), Lecture Notes in Comput. Sci. 3106, Springer (2004) 370 MR2162052
42	R W Ogburn, J Preskill, Topological quantum computation, from: "Quantum computing and quantum communications" (editor C P Williams), Lecture Notes in Comput. Sci. 1509, Springer (1999) 341 MR1750535
43	P Olum, Non-abelian cohomology and van Kampen’s theorem, Ann. of Math. 68 (1958) 658 MR0096218
44	B Poonen, Undecidable problems: a sampler, from: "Interpreting Gödel" (editor J Kennedy), Cambridge Univ. Press (2014) 211 MR3468188
45	N Y Reshetikhin, V G Turaev, Ribbon graphs and their invariants derived from quantum groups, Comm. Math. Phys. 127 (1990) 1 MR1036112
46	N Reshetikhin, V G Turaev, Invariants of 3–manifolds via link polynomials and quantum groups, Invent. Math. 103 (1991) 547 MR1091619
47	K A Ribet, On l–adic representations attached to modular forms, Invent. Math. 28 (1975) 245 MR0419358
48	D P Roberts, A Venkatesh, Hurwitz monodromy and full number fields, Algebra Number Theory 9 (2015) 511 MR3340543
49	E C Rowell, Two paradigms for topological quantum computation, from: "Advances in quantum computation" (editors K Mahdavi, D Koslover), Contemp. Math. 482, Amer. Math. Soc. (2009) 165 MR2568418
50	V G Turaev, Quantum invariants of knots and 3–manifolds, 18, de Gruyter (1994) MR1292673
51	L G Valiant, The complexity of computing the permanent, Theoret. Comput. Sci. 8 (1979) 189 MR526203
52	L G Valiant, V V Vazirani, NP is as easy as detecting unique solutions, Theoret. Comput. Sci. 47 (1986) 85 MR871466