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.




Downloads Statistics

Download Full History