[Theory] REMINDER: 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>*


On Sun, Jan 9, 2022 at 3:03 PM Mary Marre <mmarre at ttic.edu> wrote:

> *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>*
>
>
> On Mon, Jan 3, 2022 at 6:29 PM Mary Marre <mmarre at ttic.edu> wrote:
>
>> *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/20220110/deee3be5/attachment-0001.html>