List-Decodability of Poisson Point Processes

Zhang, Yihan and Vatedka, Shashank (2022) List-Decodability of Poisson Point Processes. In: 2022 IEEE International Symposium on Information Theory, ISIT 2022, 26 June 2022 through 1 July 2022, Espoo.

[img] Text
IEEE_International.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 N > 0 and L ∈ Z ≫ 2. A multiple packing is a set C of points in Rn such that any point in Rn lies in the intersection of at most L - 1 balls of radius √nN around points in C. Given a well-known connection with coding theory, multiple packings can be viewed as the Euclidean analog of list-decodable codes, which are well-studied for finite fields. In this paper, we exactly pin down the asymptotic density of (expurgated) Poisson Point Processes under a stronger notion called average-radius multiple packing. To this end, we apply tools from high-dimensional geometry and large deviation theory. This gives rise to the best known lower bound on the largest multiple packing density. Our result corrects a mistake in a previous paper by Blinovsky [Bli05]. © 2022 IEEE.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Vatedka, Shashank
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. 1We choose to stick with L ´ 1 rather than L for notational convenience. This is because in the proof, we need to examine the violation of pL ´ 1q-packing,? i.e., the existence of an L-sized subset that lies in a ball of radius nN. 2Logarithms to the base e are denoted by lnp¨q.
Uncontrolled Keywords: Coding Theory; Euclidean; Euclidean spaces; High-dimensional; Higher-dimensional; List decodability; Multiple packings; Natural generalization; Poisson point process; Sphere packings
Subjects: Electrical Engineering
Divisions: Department of Electrical Engineering
Depositing User: . LibTrainee 2021
Date Deposited: 02 Sep 2022 04:27
Last Modified: 02 Sep 2022 04:27
Publisher URL:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 10384 Statistics for this ePrint Item