Name
Abstract | ||
|---|---|---|
Let ℒ be an n-dimensional lattice, and let x be a point chosen uniformly from a large ball in ℝ
n
. In this note we consider the distribution of the distance from x to ℒ, normalized by the largest possible such distance (i.e., the covering radius of ℒ). 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 ℓ
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
protocol for the Covering Radius Problem. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/s00454-008-9123-5 | Discrete & Computational Geometry |
Keywords | Field | DocType |
Lattices,Geometrical invariants,Second moment,Covering radius,Computational complexity | Discrete mathematics,Topology,Combinatorics,Normalization (statistics),Lattice (order),Existential quantification,Physical constant,Mathematics,Second moment of area,Computational complexity theory | Journal |
Volume | Issue | ISSN |
41 | 1 | 0179-5376 |
Citations | PageRank | References |
3 | 0.41 | 5 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ishay Haviv | 1 | 91 | 9.86 |
| Vadim Lyubashevsky | 2 | 1174 | 59.91 |
| Oded Regev | 3 | 2322 | 133.33 |