Header menu link for other important links
X
List-Decodability of Poisson Point Processes
Published in Institute of Electrical and Electronics Engineers Inc.
2022
Volume: 2022-June
   
Pages: 2559 - 2564
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 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.
About the journal
JournalData powered by TypesetIEEE International Symposium on Information Theory - Proceedings
PublisherData powered by TypesetInstitute of Electrical and Electronics Engineers Inc.
ISSN21578095