New combinatorial bounds for error correcting codes
Abstract/Contents
- Abstract
- This thesis is about coding theory. Coding theory studies (error-correcting) codes, sets of strings that protect information from noise. To define a code, we typically imagine a communication setup: a sender, conventionally named Alice, wants to send a message to a receiver, conventionally named Bob, through a noisy channel, so she sends Bob an encoded message called a codeword with enough redundancy that Bob can decode the message, even in the presence of noise. The success of this protocol largely boils down to the mathematical properties of the code, the set of possible codewords Alice could send. The central challenge in coding theory is finding codes that are both ``less redundant'' (meaning Alice's encoded message is not too long) and ``more robust'' (meaning Alice and Bob's protocol can tolerate more noise). This thesis studies this central challenge in two basic contexts: deletion codes and list-decoding. In deletion codes, 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, 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. Most 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.
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2022; ©2022 |
| Publication date | 2022; 2022 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Li, Ray |
|---|---|
| Degree supervisor | Fox, Jacob, 1984- |
| Degree supervisor | Wootters, Mary |
| Thesis advisor | Fox, Jacob, 1984- |
| Thesis advisor | Wootters, Mary |
| Thesis advisor | Tan, Li-Yang |
| Degree committee member | Tan, Li-Yang |
| Associated with | Stanford University, Computer Science Department |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Ray Li. |
|---|---|
| Note | Submitted to the Computer Science Department. |
| Thesis | Thesis Ph.D. Stanford University 2022. |
| Location | https://purl.stanford.edu/qy377nm6829 |
Access conditions
- Copyright
- © 2022 by Ray Li
Also listed in
Loading usage metrics...