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 -