Computing the Theta Series
Theory of Computing, Volume 22(2140), pp. 1-30, 2026
Bibliography with links to cited articles
[1] Divesh Aggarwal, Daniel Dadush, Oded Regev, and Noah Stephens-Davidowitz: Solving the shortest vector problem in 2n time via discrete Gaussian sampling (extended abstract). In Proc. 47th STOC, pp. 733–742. ACM Press, 2015. [doi:10.1145/2746539.2746606]
[2] Dorit Aharonov and Oded Regev: Lattice problems in NP ∩ coNP. J. ACM, 52(5):749–765, 2005. Preliminary version in FOCS’04. [doi:10.1145/1089023.1089025]
[3] Miklós Ajtai: Generating hard instances of lattice problems (extended abstract). In Proc. 28th STOC, pp. 99–108. ACM Press, 1996. [doi:10.1145/237814.237838]
[4] Miklós Ajtai, Ravi Kumar, and D. Sivakumar: A sieve algorithm for the shortest lattice vector problem. In Proc. 33rd STOC, pp. 601–610. ACM Press, 2001. [doi:10.1145/380752.380857]
[5] George E. Andrews: The Theory of Partitions. Cambridge Mathematical Library. Cambridge Univ. Press, reprint of the 1976 original edition, 1984. [doi:10.1017/CBO9780511608650]
[6] David L. Applegate and Ravi Kannan: Sampling and integration of near log-concave functions. In Proc. 23rd STOC, pp. 156–163. ACM Press, 1991. [doi:10.1145/103418.103439]
[7] Wojciech Banaszczyk: New bounds in some transference theorems in the geometry of numbers. Mathematische Annalen, 296(4):625–635, 1993. [doi:10.1007/BF01445125]
[8] Richard Bellman and R. Sherman Lehman: The reciprocity formula for multidimensional theta functions. Proc. AMS, 12(6):954–961, 1961. [doi:10.1090/S0002-9939-1961-0136775-4]
[9] John William Scott Cassels: An Introduction to the Geometry of Numbers. Classics in Mathematics. Springer, Berlin, corrected reprint of the 1971 edition, 1997. [doi:10.1007/978-3-642-62035-5]
[10] Irit Dinur, Guy Kindler, Ran Raz, and Shmuel Safra: Approximating CVP to within almost-polynomial factors is NP-hard. Combinatorica, 23(2):205–243, 2003. [doi:10.1007/s00493-003-0019-y]
[11] Alan Frieze and Ravi Kannan: Log-Sobolev inequalities and sampling from log-concave distributions. Ann. Appl. Probab., 9(1):14–26, 1999. [doi:10.1214/aoap/1029962595]
[12] Alan Frieze, Ravi Kannan, and Nick Polson: Sampling from log-concave distributions. Ann. Appl. Probab., 4(3):812–837, 1994. [doi:10.1214/aoap/1177004973]
[13] Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan: Trapdoors for hard lattices and new cryptographic constructions (extended abstract). In Proc. 40th STOC, pp. 197–206. ACM Press, 2008. [doi:10.1145/1374376.1374407]
[14] Martin Grötschel, László Lovász, and Alexander Schrijver: Geometric Algorithms and Combinatorial Optimization. Volume 2 of Algorithms and Combinatorics. Springer, second edition, 1993. [doi:10.1007/978-3-642-78240-4]
[15] Ishay Haviv and Oded Regev: Tensor-based hardness of the shortest vector problem to within almost polynomial factors. Theory of Computing, 8(23):513–531, 2012. Preliminary version in STOC’07. [doi:10.4086/toc.2012.v008a023]
[16] Subhash Khot: Hardness of approximating the shortest vector problem in lattices. J. ACM, 52(5):789–808, 2005. Preliminary version in FOCS’04. [doi:10.1145/1089023.1089027]
[17] László Lovász and Santosh Vempala: The geometry of logconcave functions and sampling algorithms. Random Struct. Algor., 30(3):307–358, 2007. Preliminary version in FOCS’03. [doi:10.1002/rsa.20135]
[18] S. Thomas McCormick, Britta Peis, Robert Scheidweiler, and Frank Vallentin: A polynomial time algorithm for solving the closest vector problem in zonotopal lattices. SIAM J. Discr. Math., 35(4):2345–2356, 2021. [doi:10.1137/20M1382258]
[19] Daniele Micciancio and Shafi Goldwasser: Complexity of Lattice Problems: A Cryptographic Perspective. Volume 671 of The Springer Internat. Ser. in Engineering and Computer Science. Springer, 2002. [doi:10.1007/978-1-4615-0897-7]
[20] Daniele Micciancio and Oded Regev: Worst-case to average-case reductions based on Gaussian measures. SIAM J. Comput., 37(1):267–302, 2007. Preliminary version in FOCS’04. [doi:10.1137/S0097539705447360]
[21] Daniele Micciancio and Oded Regev: Lattice-based cryptography. In Daniel J. Bernstein, Johannes Buchmann, and Erik Dahmen, editors, Post-Quantum Cryptography, pp. 147–191. Springer, 2009. [doi:10.1007/978-3-540-88702-7_5]
[22] Daniele Micciancio and Panagiotis Voulgaris: A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations. SIAM J. Comput., 42(3):1364–1391, 2013. Preliminary version in STOC’10. [doi:10.1137/100811970]
[23] David Mumford: Tata Lectures on Theta I. With the collaboration of C. Musili, M. Nori, E. Previato and M. Stillman. Modern Birkhäuser Classics. Birkhäuser, reprint of the 1983 original edition, 2007. [doi:10.1007/978-0-8176-4577-9]
[24] David Mumford: Tata Lectures on Theta II. Jacobian theta functions and differential equations. With the collaboration of C. Musili, M. Nori, E. Previato, M. Stillman and H. Umemura. Modern Birkhäuser Classics. Birkhäuser, reprint of the 1984 original edition, 2007. [doi:10.1007/978-0-8176-4578-6]
[25] David Mumford: Tata Lectures on Theta III. With collaboration of Madhav Nori and Peter Norman. Modern Birkhäuser Classics. Birkhäuser, reprint of the 1991 original edition, 2007. Link at Google books.
[26] OpenAI: Ten advances in mathematics and theoretical computer science, August 1, 2026. See Announcement and technical exposition.
[27] Chris Peikert: An efficient and parallel Gaussian sampler for lattices. In Proc. 30th Ann. Internat. Cryptology Conf. (CRYPTO’10), pp. 80–97. Springer, 2010. [doi:10.1007/978-3-642-14623-7_5]
[28] Oded Regev and Noah Stephens-Davidowitz: An inequality for Gaussians on lattices. SIAM J. Discr. Math., 31(2):749–757, 2017. [doi:10.1137/15M1052226]
[29] Claus P. Schnorr: A hierarchy of polynomial time lattice basis reduction algorithms. Theoret. Comput. Sci., 53(2–3):201–224, 1987. [doi:10.1016/0304-3975(87)90064-8]
[30] Neil J. A. Sloane, Vinay A. Vaishampayan, and Sueli I.R. Costa: A note on projecting the cubic lattice. Discr. Comput. Geom., 46(3):472–478, 2011. [doi:10.1007/s00454-010-9280-1]
