Computer Science Thesis Oral

Monday, July 27, 2015 - 1:00pm to 3:00pm


Traffic 21 Classroom 6501 Gates & Hillman Centers


CAROL WANG, Ph.D. Student

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 efficiency and resilience. This thesis covers various areas in the field of error-correcting codes, showing how to efficiently handle errors which arise in different applications. 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. Thesis Committee: Venkatesan Guruswami (Chair) Bernhard Haeupler Ryan O’Donnell Po-Shen Loh Madhu Sudan (Microsoft Research)

For More Information, Contact:


Thesis Oral