一、报告题目

Multiple packing

二、主讲人

Yihan Zhang

三、报告时间

2022年8月15日 15:00-16:15

四、报告地点

Zoom link :https://technion.zoom.us/j/2299445207

五、摘要

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).

六、主讲人简介

Yihan Zhang received the B.Eng. degree in computer science and technology from Northeastern University, Shenyang, China, in June 2016, and the Ph.D. degree from the Department of Information Engineering, The Chinese University of Hong Kong, Hong Kong, in August 2020. He was a Post-Doctoral Researcher at the Henry and Marilyn Taub Faculty of Computer Science, Technion—Israel Institute of Technology, from October 2020 to October 2021. He has been a Post-Doctoral Researcher at the Institute of Science and Technology Austria since October 2021. His research interests include information theory, coding theory, and statistics theory.

七、主办单位

非线性期望前沿科学中心

数学与交叉科学研究中心