TY - JOUR

T1 - A note on the distribution of the distance from a lattice

AU - Haviv, Ishay

AU - Lyubashevsky, Vadim

AU - Regev, Oded

N1 - Funding Information:
V. Lyubashevsky’s research was supported by NSF ITR 0313241.
Funding Information:
O. Regev’s research was supported by an Alon Fellowship, by the Binational Science Foundation, by the Israel Science Foundation, and by the European Commission under the Integrated Project QAP funded by the IST directorate as Contract Number 015848.
Funding Information:
I. Haviv’s research was supported by the Binational Science Foundation and by the Israel Science Foundation.

PY - 2009/1

Y1 - 2009/1

N2 - Let L be an n-dimensional lattice, and let x be a point chosen uniformly from a large ball in L n . In this note we consider the distribution of the distance from x to L, normalized by the largest possible such distance (i.e., the covering radius of L). By definition, the support of this distribution is [0,1]. We show that there exists a universal constant α 2 that provides a natural "threshold" for this distribution in the following sense. For any ε>0, there exists a δ>0 such that for any lattice, this distribution has mass at least δ on [α 2-ε,1]; moreover, there exist lattices for which the distribution is tightly concentrated around α 2 (and so the mass on [α 2+ε,1] can be arbitrarily small). We also provide several bounds on α 2 and its extension to other L p norms. We end with an application from the area of computational complexity. Namely, we show that α 2 is exactly the approximation factor of a certain natural AM protocol for the Covering Radius Problem.

AB - Let L be an n-dimensional lattice, and let x be a point chosen uniformly from a large ball in L n . In this note we consider the distribution of the distance from x to L, normalized by the largest possible such distance (i.e., the covering radius of L). By definition, the support of this distribution is [0,1]. We show that there exists a universal constant α 2 that provides a natural "threshold" for this distribution in the following sense. For any ε>0, there exists a δ>0 such that for any lattice, this distribution has mass at least δ on [α 2-ε,1]; moreover, there exist lattices for which the distribution is tightly concentrated around α 2 (and so the mass on [α 2+ε,1] can be arbitrarily small). We also provide several bounds on α 2 and its extension to other L p norms. We end with an application from the area of computational complexity. Namely, we show that α 2 is exactly the approximation factor of a certain natural AM protocol for the Covering Radius Problem.

KW - Computational complexity

KW - Covering radius

KW - Geometrical invariants

KW - Lattices

KW - Second moment

UR - http://www.scopus.com/inward/record.url?scp=57849155685&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=57849155685&partnerID=8YFLogxK

U2 - 10.1007/s00454-008-9123-5

DO - 10.1007/s00454-008-9123-5

M3 - Article

AN - SCOPUS:57849155685

SN - 0179-5376

VL - 41

SP - 162

EP - 176

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 1

ER -