Volume 22, issue 6 (2018)

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

Volume 26
Issue 3, 937–1434
Issue 2, 477–936
Issue 1, 1–476

Volume 25, 7 issues

Volume 24, 7 issues

Volume 23, 7 issues

Volume 22, 7 issues

Volume 21, 6 issues

Volume 20, 6 issues

Volume 19, 6 issues

Volume 18, 5 issues

Volume 17, 5 issues

Volume 16, 4 issues

Volume 15, 4 issues

Volume 14, 5 issues

Volume 13, 5 issues

Volume 12, 5 issues

Volume 11, 4 issues

Volume 10, 4 issues

Volume 9, 4 issues

Volume 8, 3 issues

Volume 7, 2 issues

Volume 6, 2 issues

Volume 5, 2 issues

Volume 4, 1 issue

Volume 3, 1 issue

Volume 2, 1 issue

Volume 1, 1 issue

The Journal
About the Journal
Editorial Board
Editorial Interests
Editorial Procedure
Subscriptions
 
Submission Guidelines
Submission Page
Policies for Authors
Ethics Statement
 
ISSN (electronic): 1364-0380
ISSN (print): 1465-3060
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
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