Volume 18, issue 2 (2018)

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

Volume 18
Issue 6, 3133–3747
Issue 5, 2509–3131
Issue 4, 1883–2507
Issue 3, 1259–1881
Issue 2, 635–1258
Issue 1, 1–633

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
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