Volume 18, issue 2 (2018)

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

Volume 19
Issue 2, 533–1078
Issue 1, 1–532

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
Subscriptions
Editorial Board
Editorial Interests
Editorial Procedure
Submission Guidelines
Submission Page
Ethics Statement
Author Index
To Appear
ISSN (electronic): 1472-2739
ISSN (print): 1472-2747
Other MSP Journals
Identifying lens spaces in polynomial time

Greg Kuperberg

Algebraic & Geometric Topology 18 (2018) 767–778
Bibliography
1 S Aaronson, C Granade, G Kuperberg, V Russo, The complexity zoo, electronic resource
2 D Aharonov, V Jones, Z Landau, A polynomial quantum algorithm for approximating the Jones polynomial, Algorithmica 55 (2009) 395 MR2512029
3 J Edmonds, Systems of distinct representatives and linear algebra, J. Res. Nat. Bur. Standards Sect. B 71B (1967) 241 MR0229540
4 S Garnerone, A Marzuoli, M Rasetti, Efficient quantum processing of three-manifold topological invariants, Adv. Theor. Math. Phys. 13 (2009) 1601 MR2678993
5 J Hass, J C Lagarias, N Pippenger, The computational complexity of knot and link problems, J. ACM 46 (1999) 185 MR1693203
6 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
7 G Kuperberg, Knottedness is in NP, modulo GRH, Adv. Math. 256 (2014) 493 MR3177300
8 G Kuperberg, Algorithmic homeomorphism of 3–manifolds as a corollary of geometrization, preprint (2015) arXiv:1508.06720
9 G Kuperberg, How hard is it to approximate the Jones polynomial ?, Theory Comput. 11 (2015) 183 MR3354608
10 G Kuperberg, Identifying lens spaces using discrete logarithms, v1, preprint (2015) arXiv:1509.02887v1
11 G Kuperberg, Learning the exponents in a sum of two modular roots of unity, MathOverflow post (2015)
12 M Lackenby, The efficient certification of knottedness and Thurston norm, preprint (2016) arXiv:1604.00290
13 M Lackenby, S Schleimer, Lens space recognition is in NP, Oberwolfach Rep. 9 (2012) 1421 MR3156716
14 G Myerson, Unsolved problems: how small can a sum of roots of unity be?, Amer. Math. Monthly 93 (1986) 457 MR1540889
15 M A Nielsen, I L Chuang, Quantum computation and quantum information, Cambridge Univ. Press (2000) MR1796805
16 B Poonen, Undecidable problems: a sampler, from: "Interpreting Gödel" (editor J Kennedy), Cambridge Univ. Press (2014) 211 MR3468188
17 K Reidemeister, Homotopieringe und Linsenräume, Abh. Math. Sem. Univ. Hamburg 11 (1935) 102 MR3069647
18 D Rolfsen, Knots and links, 7, Publish or Perish (1976) MR0515288
19 S Schleimer, Sphere recognition lies in NP, from: "Low-dimensional and symplectic topology" (editor M Usher), Proc. Sympos. Pure Math. 82, Amer. Math. Soc. (2011) 183 MR2768660
20 P W Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput. 26 (1997) 1484 MR1471990
21 T Tao, How small can a sum of a few roots of unity be?, MathOverflow post (2010)
22 V Turaev, Torsions of 3–dimensional manifolds, 208, Birkhäuser (2002) MR1958479