Explicit Folded Reed–Solomon and Multiplicity Codes Achieve Relaxed Generalized Singleton Bounds
报告人
Zihan Zhang
Ohio State University
时 间
2025年3月18日 星期二 10:00am
在线会议
Zoom Meeting ID: 852 3183 7607
Passcode: 066806
Host
程宽 助理教授
Abstract
List-decodable codes play a crucial role in both theoretical and practical applications. By loosening the constraint of unique decoding—requiring only that the original codeword be among a small set of candidates—they can withstand nearly twice as many errors. This enhanced error resilience is fundamental to applications such as group testing and compressed sensing. Beyond error correction, their well-structured mathematical properties enable broader applications in fields like pseudorandomness, computational complexity, and cryptography.
A central and fundamental question in coding theory is what kinds of codes are optimally list-decodable. Previously, all known constructions either relied on randomness or required significantly larger list sizes. In this talk, I will present recent progress demonstrating the first explicit codes that are list-decodable to capacity with the optimal list size. More concretely, I will show that any “appropriate” folded Reed-Solomon codes and multiplicity codes are almost optimally list-decodable, fully resolving an open problem of Guruswami–Rudra [STOC 2006]. I will discuss the high-level ideas behind these constructions and outline directions for future research.
These results are based on joint work with Yeyuan Chen.
Biography
Zihan Zhang is currently a PhD student in the Department of Computer Science and Engineering at the Ohio State University under the guidance of Prof. Zeyu Guo. His research interests lie broadly in theoretical computer science, with a particular emphasis on pseudorandomness, coding theory, combinatorics, and applications of coding theory into cryptography. One of his works on list decoding was recognized with the Danny Lewin Best Student Paper Award at STOC 2025. His bachelor’s thesis received the Silver Prize in the ICCM Best Thesis Award (formerly known as the New World Mathematics Award, NWMA).
往 期 讲 座
静5杰出讲座回顾 | Bart Selman教授谈人工智能如何加速科学与数学发现
静5前沿讲座回顾 | 姚鹏晖教授谈Pauli analysis在量子算法中的应用
静5青年讲座回顾 | 许逸伦博士谈物理启发的生成模型最新进展
静5前沿讲座回顾 | Dr. Alan Szepieniec介绍区块链中可扩展且隐私保护的存储技术
— 版权声明 —
本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。
点“阅读原文”查看海报
