Explicit Lossless Expanders and Interactive Codes

One of the main results in this thesis is the first explicit construction of two-sided lossless expanders. A lossless expander is a sparse graph where every small set of vertices has nearly as many neighbors as its sparsity permits. While a random graph is a lossless expander with high probability, constructing lossless expanders explicitly remained open for many years. We resolve this problem by identifying a connection to the relatively new area of high-dimensional expanders.

 

Going beyond lossless expanders, we further explore applications of what we call "modern expanders"—expander constructions developed over the last two decades—to error-correcting codes. Our contributions include a simple, near-optimal construction of $\eps$-balanced codes, as well as new constructions of locally testable codes.

 

Finally, we study the task of noise-resilient communication in the presence of feedback. We give error-correcting schemes that either require less feedback or achieve greater noise resilience than was previously known. We also give the first error-correcting codes for the streaming setting, where the decoder operates under strict space constraints.

 

Committee: Yael Tauman Kalai (advisor), Vinod Vaikuntanathan (advisor), Dor Minzer.