List Decoding of Direct Sum Codes
List Decoding of Direct Sum Codes
复制标题
直和码的列表解码
DOI：
10.1137/1.9781611975994.85
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Tulsiani, Madhur
中科院分区：
文献类型：
--
作者：
Alev, Vedat Levi;Jeronimo, Fernando Granha;Quintana, Dylan;Srivastava, Shashank;Tulsiani, Madhur
根据一个合适的一致超图，我们考虑通过对码字的“局部视图”应用诸如ask-XOR之类的操作“提升”基码所获得的码族。k- xor运算产生的直接和编码在[Ta-Shma， STOC 2017]和[Dinur and Kaufman， FOCS 2017]的作品中使用。我们给出了这类提升码的列表解码的一般框架，只要基码允许唯一的解码算法，并且用于提升的超图满足一定的展开性质。我们证明了在一个足够强的展开图上的长度行走的集合和对应于高维展开图的超图确实满足这些性质。通过实例化我们的框架，我们得到了对应于上述超图族的直接和提升的列表解码算法。使用直接和和直接乘积之间的已知联系，我们还恢复（并加强）Dinur等人[SODA 2019]关于直接乘积提升的列表解码的最新结果。我们的框架依赖于平方和（SOS） SDP层次结构给出的松弛来解决各种约束满足问题（csp）。我们将恢复与给定（可能损坏的）字最接近的码字的问题视为找到CSP实例的最佳解决方案。实例中的约束对应于提升超图的边，解被限制在基代码中。我们证明了一些作者最近在某些扩展超图上（近似）求解csp的算法也产生了这种提升码的解码算法。通过要求SOS解决方案最小化负熵的凸代理，我们将框架扩展到列表解码。我们证明了这确保了SOS解决方案的覆盖属性，并且在几个SOS算法中使用的“条件和圆”方法可以用来恢复所需的码字列表。
We consider families of codes obtained by “lifting” a base code through operations such ask-XOR applied to “local views” of codewords of , according to a suitablek-uniform hypergraph. Thek-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 indeed satisfied by the collection of lengthkwalks on a sufficiently strong expanding graph, and by hypergraphs corresponding to high-dimensional expanders. Instantiating our framework, we obtain list decoding algorithms for direct sum liftings corresponding to the above hypergraph families. Using known connections between direct sum and direct product, we also recover (and strengthen) 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 (possibly corrupted) word, as finding the optimal solution to an instance 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 . We show that recent algorithms for (approximately) solving CSPs on certain expanding hypergraphs by some of the authors 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.
登录
查看更多内容
列表可解码线性回归
DOI：
--
发表时间：
2019
期刊：
Advances in neural information processing systems
影响因子：
--
作者：
Karmalkar, Sushrut;Klivans, Adam;Kothari, Pravesh
通讯作者：
Kothari, Pravesh
通过全局相关性舍入半定编程层次结构
DOI：
10.1109/focs.2011.95
发表时间：
2011
期刊：
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
B. Barak;P. Raghavendra;David Steurer
通讯作者：
David Steurer
线性时间可编码和列表可解码代码
DOI：
10.1145/780542.780562
发表时间：
2003
期刊：
Inf. Comput.
影响因子：
--
作者：
V. Guruswami;P. Indyk
通讯作者：
P. Indyk
使用双采样器进行列表解码
DOI：
--
发表时间：
2018
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Irit Dinur;P. Harsha;T. Kaufman;I. Navon;A. Ta
通讯作者：
A. Ta
ķ 型拉马努金复合体的显式构造
DOI：
--
发表时间：
2005
期刊：
European journal of combinatorics (Print)
影响因子：
--
作者：
A. Lubotzky;Beth Samuels;U. Vishne
通讯作者：
U. Vishne