Error-correcting codes were originally developed in the context of reliable delivery of data over a noisy communication channel and continue to be widely used in communication and storage systems. Over time, errorcorrecting codes have also been shown to have several exciting connections to areas in theoretical computer science. Recently, there have been several advances including new constructions of efficient codes as well as coding in different settings. This thesis explores several new directions in modern coding theory. To this end, we:

1. Provide a theoretical analysis of polar codes, which were a breakthrough made by Arikan in the last decade [Ar09]. We show that polar codes over prime alphabets are the first explicit construction of efficient codes to provably achieve Shannon capacity for symmetric channels with polynomially fast convergence. We introduce interesting new techniques involving entropy sumset inequalities, which are an entropic analogue of sumset inequalities studied in additive combinatorics.

2. Consider the recent problem of coding for two-party interactive communication, in which two parties wish to execute a protocol over a noisy interactive channel. Specifically, we provide an explicit interactive coding scheme for oblivious adversarial errors and bridge the gap between channel capacities for interactive communication and one-way communication.

3. Study the problem of list decodability for codes. We resolve an open question about the list decodability of random linear codes and show surprising connections to the field of compressed sensing, in which we provide improved bounds on the number of frequency samples needed for exact reconstruction of sparse signals (improving upon the work of Candès and Tao [CT06] as well as Rudelson and Vershynin [RV08]).

4. Study locally-testable codes and affine invariance in codes. Specifically, we investigate the limitations posed by local testability, which has served as an important notion in the study of probabilistically checkable proofs (PCPs) and hardness of approximation.

201 pages

Thesis Committee:
Venkatesan Guruswami (Chair)
Bernhard Haeupler
Gary Miller
Emmanuel Abbe (Princeton University)

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

Return to: SCS Technical Report Collection
School of Computer Science