Lower bounds for multiple packing
Download
No fulltext has been uploaded. References only!
Conference Paper
| Published
| English
Scopus indexed
Author
Zhang, YihanISTA
;
Vatedka, Shashank

Department
Abstract
We study the problem of high-dimensional multiple packing in Euclidean space. Multiple packing is a natural generalization of sphere packing and is defined as follows. Let P, N > 0 and L∈Z≥2. A multiple packing is a set C of points in Bn(0–,nP−−−√) such that any point in ℝ n lies in the intersection of at most L – 1 balls of radius nN−−−√ around points in C. 1 In this paper, we derive two lower bounds on the largest possible density of a multiple packing. These bounds are obtained through a stronger notion called average-radius multiple packing. Specifically, we exactly pin down the asymptotics of (expurgated) Gaussian codes and (expurgated) spherical codes under average-radius multiple packing. To this end, we apply tools from high-dimensional geometry and large deviation theory. The bound for spherical codes matches the previous best known bound which was obtained for the standard (weaker) notion of multiple packing through a curious connection with error exponents [Bli99], [ZV21]. The bound for Gaussian codes suggests that they are strictly inferior to spherical codes.
Publishing Year
Date Published
2022-08-03
Proceedings Title
2022 IEEE International Symposium on Information Theory
Publisher
IEEE
Volume
2022
Page
3085-3090
Conference
ISIT: International Symposium on Information Theory
Conference Location
Espoo, Finland
Conference Date
2022-06-26 – 2022-07-01
ISBN
ISSN
IST-REx-ID