Header menu link for other important links
X
Lower bounds for Multiple Packing
Published in Institute of Electrical and Electronics Engineers Inc.
2022
Volume: 2022-June
   
Pages: 3085 - 3090
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. © 2022 IEEE.
About the journal
JournalData powered by TypesetIEEE International Symposium on Information Theory - Proceedings
PublisherData powered by TypesetInstitute of Electrical and Electronics Engineers Inc.
ISSN21578095