Error-correcting codes give efficient ways to store and recover information, even when the information has been corrupted. They have seen wide applicability in areas like software and communication, where they allow for improvements in both redundancy and resilience.

This thesis covers various areas in the field of error-correcting codes, addressing problems which arise in different applications and error models. One such area is that of list-decoding, a model in which the decoder may output multiple possible decodings, allowing for correction from a larger number of errors. We give an explicit construction of good codes which are efficiently list-decodable up to an information theoretically optimal fraction of errors. The framework we have developed for decoding, the linear-algebraic method, has proven to be a powerful tool for designing and decoding codes.

We extend our techniques to construct the first nontrivially list-decodable codes with high rate for the rank metric, a model which has applications in wireless network communication. We also construct the first explicit deletion codes correcting a constant fraction of deletions with rate approaching one, and correcting a fraction of deletions approaching one with constant rate. The central theme of this thesis is that effective communication is possible, even for these very different models.

115 pages

Thesis Committee:
Venkatesan Guruswami (Chair)
Ryan O'Donnell
Bernhard Haeupler
Po-Shen Loh
Madhu Sudan (Microsoft Research)

Frank Pfenning, Head, Computer Science Department
Andrew W. Moore, Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by [email protected]