List-Decodability of Poisson Point Processes
Yihan Zhang, Shashank Vatedka · 2022 IEEE International Symposium on Information Theory (ISIT) · 2022
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 \in {\mathbb{Z}} \geq 2$. A multiple packing is a set ${\mathcal{C}}$ of points in ${{\mathbb{R}}^n}$ such that any point in ${{\mathbb{R}}^n}$ lies in the intersection of at most L – 1 balls of radius $\sqrt {nN} $ around points in ${\mathcal{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].