Computer Science Thesis Oral

Friday, May 8, 2020 - 9:30am

Location:

Virtual Presentation Remote Access Enabled - Zoom

Speaker:

NICOLAS ALEXANDER RESCH, Ph.D. Student https://www.cs.cmu.edu/~nresch/

List-Decodable Codes: (Randomized) Constructions and Applications

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 (p, L)-list-decodable code C guarantees that for any received word z, the number of codewords at distance at most p from z 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 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.

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

Zoom Participation Enabled.  See announcement.

For More Information, Contact:

Keywords:

Thesis Oral