LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
Probabilistic Guarantees to Explicit Constructions: Local Properties of Linear Codes
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

Probabilistic Guarantees to Explicit Constructions: Local Properties of Linear Codes

74 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
IAS

Nikhil Shagrithaya, a researcher from the University of Michigan, presents a framework for derandomizing random linear codes at this Institute for Advanced Study Computer Science/Discrete Mathematics Seminar. He addresses local properties of codes, a category that includes minimum distance, list-decoding, list-recovery, and perfect hashing, and extends the classical Alon-Edmonds-Luby construction through a new formalism called local coordinate-wise linear properties, developed with Zohar Mosheiff and others at FOCS 2025. The main result gives explicit code constructions matching the optimality of random linear codes for these properties, at the cost of larger alphabet size, including the first explicit list-recoverable codes with output list sizes matching random constructions. Drawing on joint work with Fernando Granha Jeronimo, the talk lays out the background needed to state the result and sketches its proof. The audience is specialists in coding theory and theoretical computer science.

At a glance

Lecture facts

Runtime compared with the other 148 Computer Science lectures
Runtime1 h 14 m
Compared with Computer ScienceLonger than 51%
Source channelInstitute for Advanced Study (YouTube)