Search Mailing List Archives
[theory-seminar] Thesis defense
rayyli at stanford.edu
Mon Mar 7 09:16:03 PST 2022
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
Computer Science Department
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...
More information about the theory-seminar