Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Thesis defense

Ray Li rayyli at
Mon Mar 7 09:16:03 PST 2022

Hi All,

I'm defending my thesis tomorrow Tuesday 3/8 at 2:15pm, and I would be delighted to see you there!


Title: New Combinatorial Bounds for Error-Correcting Codes

Ray Li
Computer Science Department
Stanford University
Advisors: Jacob Fox and Mary Wootters

Time: Tuesday, March 8th, 2:15pm
Location: Gates 415

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 do so, Alice encodes the message with an error-correcting code so that Bob can recover the message, even in the presence of noise. This thesis addresses 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. This setup is motivated by applications such as DNA storage, magnetic recording, and internet transmission. Though deletion codes is an old topic, our understanding was poor compared to other errors like substitutions and erasures, and many basic questions remained open until recently. We contribute to this recent progress, answering 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 Alice and Bob to tolerate more noise (approximately twice as much). For this reason (and others), list-decoding finds various applications such as group testing, compressed sensing, algorithm design, pseudorandomness, complexity, and cryptography. All applications require explicit list-decodable codes, but our best list-decodable codes are often nonexplicit random codes. Towards finding optimal explicit list-decodable codes, we show stronger list decoding results for more-structured ensembles of codes, such as random linear codes and random Reed Solomon codes.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list