Any Errors in this Dissertation are Probably Fixable: Topics in Probability and Error Correcting Codes.

Abstract

We study two problems in coding theory, list-decoding and local-decoding. We take a probabilistic approach to these problems, in contrast to more typical algebraic approaches.

In list-decoding, we settle two open problems about the list-decodability of some well-studied ensembles of codes. First, we show that random linear codes are optimally list-decodable, and second, we show that there exist Reed-Solomon codes which are (nearly) optimally list-decodable. Our approach uses high-dimensional probability. We extend this framework to apply to a large family of codes obtained through random operations.

In local-decoding, we use expander codes to construct locally-correctible linear codes with rate approaching 1. Until recently, such codes were conjectured not to exist, and before this work the only known constructions relied on algebraic, rather than probabilistic and combinatorial, methods.