Speaker:Zhang Yihan, Post-Doctoral Researcher, Institute of Science and Technology Austria

Date:August 15, 2022

Time:15:00-16:15

Location:Zoom

Sponsor:Research Center for Mathematics and Interdisciplinary Sciences

Research Center for Nonlinear Expectation

Abstract:

The sphere packing problem seeks the largest (normalized logarithmic) density of a constellation of disjoint Euclidean balls of equal radius. With the gap between the trivial Minkowski's volume-packing lower bound and the seminal Cohn--Elkies linear-programming (LP) upper bound, the optimal density remains a holy grail open question.In this talk we consider the following natural generalization of sphere packing, known as multiple packing. An $L$-multiple packing is a collection of equal-radius balls that are allowed to overlap with multiplicity at most $L$, i.e., each point in the space lies in the intersection of at most $L$ balls. (Note that a 1-packing is a standard sphere packing.) Besides being mathematically interesting in its own right, the notion of multiple packing is motivated by list decoding in coding theory.

In this talk, I will present various upper and lower bounds for multiple packing. Various constructions will be considered, giving rise to various lower bounds, one of which turns out to be the best known. The proof uses, among others, large deviation theory and error exponents for Gaussian channels. This latter one demonstrates a curious connection between a purely combinatorial quantity (list decoding radius) and an average-case quantity (error exponent). We feel that this connection might be of independent interests. As for upper bounds, a notable difficulty is the unavailability of the analogue of the LP framework for multiple packing. We therefore resort to the "second tightest" bounding technique which is based on a combination of Plotkin-type bound and Elias--Bassalygo-type bound paralleling those in classical coding theory.

This talk will perhaps be divided into several parts, depending on how fast we proceed. No background in information / coding theory will be assumed. Based on joint work with Shashank Vatedka(arXiv: 2107.05161).

For more information, please visit:

https://www.view.sdu.edu.cn/info/1020/168263.htm