一、报告题目:The Exact Three-Parameter Trade-off in List Reconstruction for Multiple Burst Errors
二、报告人:余文俊 副教授
三、时 间:2026年11月19日(周四) 14:30-15:30
四、地 点: A2-209
报告摘要:We study optimal reconstruction codes over the multiple-burst substitution channel. Our main contribution is establishing a trade-off between the error-correction capability of the code, the number of reads used in the reconstruction process, and the decoding list size. We show that over a channel that introduces at most $t$ bursts, we can use a length-$n$ code capable of correcting $\epsilon$ errors, with $\Theta(n^\rho)$ reads, and decoding with a list of size $O(n^\lambda)$, where $t-1=\epsilon+\rho+\lambda$. In the process of proving this, we establish sharp asymptotic bounds on the size of error balls in the burst metric. More precisely, we prove a Johnson-type lower bound via Kahn's Theorem on large matchings in hypergraphs, and an upper bound via a novel variant of Kleitman's Theorem under the burst metric, which might be of independent interest.
Beyond this, we derive several related results using a variety of combinatorial techniques. In particular, along with tools from recent advances in discrete geometry, we improve the classical Gilbert-Varshamov bound for multiple bursts, and determine the minimum redundancy required for reconstruction codes with polynomially-many reads. We also propose an efficient list-reconstruction algorithm that achieves the above guarantees, based on a majority-with-threshold decoding scheme.
报告人简介:余文俊,西安电子科技大学数学与交叉科学研究院菁英副教授。2021年博士毕业于中国科学技术大学数学科学学院;2021年-2023年在华为分布式存储部门担任高级工程师;2023年-2026年在以色列本古里安大学从事博士后,合作导师为Moshe Schwartz。主要从事编码理论、组合数学及其在信息存储系统中的应用研究,研究方向包括分布式存储编码;DNA 数据存储编码、插入删除纠错码、重构码、列表重构码;多类新型编码方案设计以及极值组合问题等。围绕高可靠、高效率信息存储与传输中的基础理论问题,开展了系统研究,特别关注组合结构在复杂存储场景中的编码构造与性能分析。相关研究成果发表于 IEEE Transactions on Information Theory、IEEE International Symposium on Information Theory、Journal of Combinatorial Theory, Series A、European Journal of Combinatorics、Designs, Codes and Cryptography 等国际学术期刊/会议11篇。其中 CCF A 类论文 7 篇。
欢迎广大师生参加! 联系人:加拿大28
图论团队