
In an integral lattice counting the number of vectors of (Euclidean) length \(d\) is \(\#\)P-complete [see \textit{L. G. Valiant}, Theor. Comput. Sci. 8, 189--201 (1979; Zbl 0415.68008)] and at least as hard as integer factorization. For lattice rank \(r\) and a basis of \(s\) bits a deterministic algorithm is presented with time \(2^{O(rs+\log d)}\). The length is a quadratic form corresponding to a theta function and the vector count is essentially the \(d\)th coefficient of its Fourier expansion. Since the theta function is a modular form, a basis of (say) Eisenstein series can be constructed. There are painful details involving the fact that unimodular forms do not have even diagonal except for special cases (e.g., of rank 8) so that the dimension has to be augmented to a multiple of 8 to remain in the modular group. The reversion of this complexity problem to its classical theory is in the author's words ``long overdue''.
Computer Networks and Communications, Applied Mathematics, Modular forms, modular forms, Lattices, Complexity, #P-complete, theta functions, algorithms, Theoretical Computer Science, Computational Theory and Mathematics, lattices, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), Quadratic forms (reduction theory, extreme forms, etc.), complexity, Algorithms, Number-theoretic algorithms; complexity, \(\#\)P-complete
Computer Networks and Communications, Applied Mathematics, Modular forms, modular forms, Lattices, Complexity, #P-complete, theta functions, algorithms, Theoretical Computer Science, Computational Theory and Mathematics, lattices, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), Quadratic forms (reduction theory, extreme forms, etc.), complexity, Algorithms, Number-theoretic algorithms; complexity, \(\#\)P-complete
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
