@article{Adventures:3032,
      recid = {3032},
      author = {Quintana, Dylan},
      title = {Adventures in Decoding Direct Sum Codes},
      publisher = {University of Chicago},
      school = {Ph.D.},
      address = {2021-06},
      pages = {208},
      abstract = {Our adventures take us through several problems related to  decoding a class of error-correcting codes known as direct  sum codes. These codes are obtained from a base code  $\mathcal{C}_0 \subseteq \mathbb{F}_2^n$ by summing the  entries of each codeword on a collection of subsets $W  \subseteq [n]^k$ to yield a code $\mathcal{C} \subseteq  \mathbb{F}_2^{W}$. If the collection $W$ has a particular  expansion property, the resulting direct sum code  $\mathcal{C}$ will have a large minimum distance and (as we  show) an efficient decoding algorithm.

In our first  adventure (Chapter 2, joint work with Vedat Levi Alev,  Fernando Granha Jeronimo, Shashank Srivastava, and Madhur  Tulsiani), we develop a list decoding algorithm for a  generalization of direct sum codes where the direct sum can  be replaced by any suitable ``lifting'' operation. The  algorithm creates a Sum-of-Squares program for list  decoding, the solution to which allows the desired list of  codewords to be recovered through rounding. We apply the  general decoding framework to obtain list decoding  algorithms for direct sum codes constructed using a  collection $W$ which is either the set of walks of $k$  vertices on an expander graph or the set of $k$-sized faces  of a high-dimensional expander.

Our second adventure  (Chapter 3, joint work with Fernando Granha Jeronimo,  Shashank Srivastava, and Madhur Tulsiani) is adapting the  results of Chapter 2 to decode Ta-Shma's [STOC 2017] direct  sum codes. These codes are $\varepsilon$-balanced, meaning  any two codewords have distance between $1/2-\varepsilon/2$  and $1/2+\varepsilon/2$, and have rate nearly achieving the  Gilbert--Varshamov bound of $\Omega(\varepsilon^2)$.  Decoding is accomplished using the direct sum list decoding  framework in an inductive process that sidesteps its  suboptimal parameter requirements. This process can perform  both unique and list decoding for Ta-Shma's codes, though  at a list decoding radius smaller than the minimum  distance.},
      url = {http://knowledge.uchicago.edu/record/3032},
      doi = {https://doi.org/10.6082/uchicago.3032},
}