BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1780
DTSTAMP:20261009T050847Z
SUMMARY:Probabilistic Guarantees to Explicit Constructions: Local Propertie
 s of Linear Codes
DESCRIPTION:Speaker: Nikhil Shagrithaya (University of Michigan)\n\nAbstrac
 t: \nWe 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 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\, Moshe
 iff\, and Shagrithaya (2025). The main theorem demon-strates that if rando
 m linear codes satisfy the complement of an LCL property P with high proba
 bility\, then one can construct explicit codes satisfying the complement o
 f P as well\, with an enlarged yet constant alphabet size. This gives the 
 first explicit constructions for list recovery\, as well as special cases 
 (e.g.\, list recovery with erasures\, zero-error list recovery\, perfect h
 ash matrices)\, with parameters matching those of random linear codes. Mor
 e broadly\, our constructions realize the full range of parameters associa
 ted with these properties at the same level of optimality as in the random
  setting\, thereby offering a systematic pathway from probabilistic guaran
 tees to explicit codes that attain them. Furthermore\, our derandomization
  of random linear codes also admits efficient (list) decoding via recently
  developed expander-based decoders.\n \nBio: Nikhil Shagrithaya is a rec
 ent Ph.D. graduate from the University of Michigan\, Ann Arbor\, where he 
 was advised by Prof. Mahdi Cheraghchi. His research interests lie in codin
 g theory\, pseudorandomness\, and computational complexity theory. His rec
 ent work has focused on understanding the behavior of linear codes in the 
 context of local properties\, such as list-decoding and list-recovery.\n
URL:https://www.tcs.tifr.res.in/web/events/1780
DTSTART;TZID=Asia/Kolkata:20261021T160000
DTEND;TZID=Asia/Kolkata:20261021T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR