论文标题
列表解码直接总和代码
List Decoding of Direct Sum Codes
论文作者
论文摘要
根据合适的$ k $ -K $ -K $ -Surominsion Hypergraph，我们考虑通过“升起”基本代码$ \ MATHCAL {c} $获得的代码家族。 $ k $ - XOR操作产生了[Ta-Shma，Stoc 2017]和[Dinur and Kaufman，focs 2017]的作品中使用的直接总和编码。 只要基本代码接受独特的解码算法，并且用于提升的超图可满足某些扩展属性，我们就会提供一个通用列表解码此类升起的代码的通用框架。我们表明，通过在扩展器图上收集了长度$ k $ walks的收集，以及与高维扩张器相对应的超图。实例化我们的框架，我们获得了上述HyperGraph家族的直接总和来解码算法的列表。使用直接总和和直接产品之间的已知连接，我们还恢复了Dinur等人的最新结果。 [SODA 2019]在直接产品提升的列表解码上。 我们的框架依赖于解决各种约束满意度问题（CSP）的SDP层次结构（SOS）SDP层次结构的放松。我们将恢复最接近给定单词的最接近的代码字的问题视为找到CSP的最佳解决方案。该实例中的约束对应于提起超图的边缘，解决方案仅限于基本代码$ \ MATHCAL {C} $中。我们表明，（大约）在某些扩展的超图上求解CSP的算法也产生了用于此类提升代码的解码算法。 我们通过需要SOS解决方案来最大程度地减少负熵的凸代理来扩展框架以列出解码。我们表明，这确保了SOS解决方案的覆盖属性，并且可以使用多种SOS算法中使用的“条件和圆形”方法来恢复所需的代码字列表。
We consider families of codes obtained by "lifting" a base code $\mathcal{C}$ through operations such as $k$-XOR applied to "local views" of codewords of $\mathcal{C}$, according to a suitable $k$-uniform hypergraph. The $k$-XOR operation yields the direct sum encoding used in works of [Ta-Shma, STOC 2017] and [Dinur and Kaufman, FOCS 2017]. We give a general framework for list decoding such lifted codes, as long as the base code admits a unique decoding algorithm, and the hypergraph used for lifting satisfies certain expansion properties. We show that these properties are satisfied by the collection of length $k$ walks on an expander graph, and by hypergraphs corresponding to high-dimensional expanders. Instantiating our framework, we obtain list decoding algorithms for direct sum liftings on the above hypergraph families. Using known connections between direct sum and direct product, we also recover the recent results of Dinur et al. [SODA 2019] on list decoding for direct product liftings. Our framework relies on relaxations given by the Sum-of-Squares (SOS) SDP hierarchy for solving various constraint satisfaction problems (CSPs). We view the problem of recovering the closest codeword to a given word, as finding the optimal solution of a CSP. Constraints in the instance correspond to edges of the lifting hypergraph, and the solutions are restricted to lie in the base code $\mathcal{C}$. We show that recent algorithms for (approximately) solving CSPs on certain expanding hypergraphs also yield a decoding algorithm for such lifted codes. We extend the framework to list decoding, by requiring the SOS solution to minimize a convex proxy for negative entropy. We show that this ensures a covering property for the SOS solution, and the "condition and round" approach used in several SOS algorithms can then be used to recover the required list of codewords.
