Coding theory is concerned with the design of error-correcting codes, which are combinatorial objects permitting the transmission of data through unreliable channels. List-decodable codes, introduced by Elias and Wozencraft in the 1950's, are a class of codes which permit nontrivial protection of data even in the presence of extremely high noise. Briefly, a (ρ, L)-list-decodable code C ⊆ Σⁿ guarantees that for any 𝓏 ∈ Σⁿ the number of code-words at distance at most ρ from 𝓏 is bounded by L. In the past twenty years, they have not only become a fundamental object of study in coding theory, but also in theoretical computer science more broadly. For example, researchers have uncovered connections to pseudorandom objects such as randomness extractors, expander graphs and pseudorandom generators, and they also play an important role in hardness of approximation.

The primary focus of this thesis concerns the construction of list-decodable codes. Specifically, we consider various random ensembles of codes, and show that they achieve the optimal tradeoff between decoding radius and rate (in which case we say that the code "achieves capacity"). Random linear codes constitute the ensemble receiving the most attention, and we develop a framework for understanding when a broad class of combinatorial properties are possessed by a typical linear code. Furthermore, we study random low-density parity-check (LDPC) codes, and demonstrate that they achieve list-decoding capacity with high probability. We also consider random linear codes over the rank metric,a linear-algebraic analog of the Hamming metric, and provide improved list-decoding guarantees.

We also provide non-randomized (i.e., explicit) constructions of list-decodable codes. Specifically, by employing the tensoring operation and some other combinatorial tricks, we obtain capacity achieving list-decodable codes with near-linear time decoding algorithms. Furthermore, the structure of these codes allows for interesting local decoding guarantees.

Finally, we uncover new connections between list-decodable codes and pseudorandomness. Using insights gleaned from recent constructions of list-decodable codes in the rank metric, we provide a construction of lossless dimension expanders, which are a linear-algebraic analog of expander graphs.

222 pages

Thesis Committee:
Venkatesan Guruswami (Co-Chair)
Bernhard Haeupler (Co-Chair)
Ryan O'Donnell
Madhu Sudan (Harvard University)

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu