Volume - 13 | Issue-1
Volume - 13 | Issue-1
Volume - 13 | Issue-1
Volume - 13 | Issue-1
Volume - 13 | Issue-1
Let f : R n −→R be a positive definite quadratic form and let y∈R n be point. We present a fully polynomial randomized approximation scheme (FPRAS) for computing ,∑ ⅇ −????(????) ???????????? ???? , provided the eigenvalues of f lie in the interval roughly between s and es and for computing∑ ⅇ −????(????−????) ???????????? ???? provided the eigenvalues of f lie in the interval roughly between e−s and s −1 for some s ≥ 3. To compute the first sum, we represent it as the integral of an explicit log-concave function on Rn, and to compute the second sum, we use the reciprocity relation for theta functions. Choosing s ∼ log n, we apply the results to test the existence of sufficiently many short integer vectors in a given subspace L ⊂ Rn or in the vicinity of L