Lower bounds for Multiple Packing

Zhang, Yihan and Vatedka, Shashank (2022) Lower bounds for Multiple Packing. In: 2022 IEEE International Symposium on Information Theory, ISIT 2022, 26 June 2022 through 1 July 2022, Espoo.

[img] Text
Proceedings_I.pdf - Published Version
Restricted to Registered users only

Download (1MB) | Request a copy


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.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Vatedka, Shashankhttps://orcid.org/0000-0003-2384-9392
Item Type: Conference or Workshop Item (Paper)
Additional Information: YZ has received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement No 682203-ERC-[Inf-Speed-Tradeoff]. The work of SV was supported by a seed grant from IIT Hyderabad and SRG/2020/000910 by SERB (DST), India.
Uncontrolled Keywords: Asymptotics; Euclidean spaces; Gaussian codes; High-dimensional; Higher-dimensional; Low bound; Multiple packings; Natural generalization; Sphere packings; Spherical codes
Subjects: Electrical Engineering
Divisions: Department of Electrical Engineering
Depositing User: . LibTrainee 2021
Date Deposited: 02 Sep 2022 04:45
Last Modified: 02 Sep 2022 04:45
URI: http://raiith.iith.ac.in/id/eprint/10386
Publisher URL: http://doi.org/10.1109/ISIT50566.2022.9834443
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 10386 Statistics for this ePrint Item