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

• Admission

Zoom Meeting ID: 852 3183 7607

Passcode: 066806