[Theory] 1/10 Talks at TTIC: Ray Li, Stanford University

[Mary Marre]

*When:*      Monday, January 10th at* 11:00 am CT*



*Where:*     Zoom Virtual Talk (*register in advance here
<https://uchicagogroup.zoom.us/webinar/register/WN_HmAUeR9XSMubFowpjq2DzA>*)


*Who: *       Ray Li, Stanford University



*Title:*        Two Stories in Coding Theory

*Abstract:*

Error-correcting codes protect information from noise. In the standard
setup, a sender, Alice, wants to send a message through a noisy channel to
a receiver, Bob. To protect the message from noise, Alice encodes the
message with an error-correcting code so that Bob can recover the message
even in the presence of noise. I will talk about fundamental challenges in
two basic coding theory contexts: deletion codes and list-decoding.



In deletion codes (Levenshtein '66, Ullman '67), the noisy channel
transmits a subsequence of Alice's encoded message. Though deletion codes
is an old topic, our understanding was poor compared to other errors like
bit-flips and erasures, and many basic questions remained open until
recently. I will talk about some of this recent progress, focusing on work
that answers one extremely basic question: can positive rate binary codes
correct a worst-case deletion fraction approaching the natural limit of 1/2?



In list decoding (Elias '57, Wozencraft '58), Bob only needs to output a
small list of messages containing the correct message. This relaxation
allows the protocol to tolerate more noise (approximately twice as much).
For this reason (and others), list-decoding finds various applications such
as communications, group testing, compressed sensing, pseudorandomness,
complexity, and cryptography. All applications require explicit
list-decodable codes, but our best list-decodable codes are often non
explicit random codes. Towards finding optimal explicit list-decodable
codes, I will talk about recent progress studying more-structured ensembles
of codes, such as random linear codes and random Reed Solomon codes.

*Host*: *Madhur Tulsiani* <madhurt at ttic.edu>



Mary C. Marre
Faculty Administrative Support
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Chicago, IL  60637*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20220103/a99e8e5e/attachment.html>