Date: March 2, 2026
Time: 3:45-5 p.m.
Location: Computing and Information Science Building, Room 450 or Click here to attend via Zoom
Speaker: Nikhil Shagrithaya
Abstract: We present a general framework for derandomizing random linear codes with respect to a broad class of properties, known as local properties, which encompass several standard notions such as minimum distance, list-decoding, list-recovery, and perfect hashing. Our approach extends the classical Alon-Edmonds-Luby (AEL) construction through a modified formalism of local coordinate-wise linear (LCL) properties, introduced by Levi, Mosheiff, and Shagrithaya (FOCS 2025).
The main result shows that we can obtain explicit constructions of codes achieving LCL properties at the same level of optimality as random linear codes, with the cost of increased alphabet size. This gives the first explicit constructions of list-recoverable codes having output list sizes that match those of random linear codes, among other results.
In this talk we will give the necessary background required to formulate the main result, as well as a sketch of its proof.
Based on joint work with Fernando Granha Jeronimo.
Bio: Nikhil Shagrithaya is a final-year Ph.D. student at the University of Michigan, Ann Arbor, advised by Prof. Mahdi Cheraghchi. His research interests lie in coding theory, pseudorandomness, and computational complexity theory. His recent work has focused on understanding the behavior of linear codes in the context of local properties, such as list-decoding and list-recovery.