Speaker: Zihan Zhang, PhD student in the Department of Computer Science and Engineering at the Ohio State University under the guidance of Prof. Zeyu Guo.

Time: 10:00 a.m., Mar 18, 2025, GMT+8

Venue: Online: Zoom Meeting ID: 852 3183 7607, Passcode: 066806

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.

Source: Center on Frontiers of Computing Studies, PKU