List Decoding with Double Samplers
List Decoding with Double Samplers
复制标题
使用双采样器进行列表解码
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
A. Ta
中科院分区：
文献类型：
--
作者：
Irit Dinur;P. Harsha;T. Kaufman;I. Navon;A. Ta
我们开发了Dinur和Kaufman首次提出的“双抽样器”的概念[Proc。第58个焦点，2017年]，是具有其他组合特性的采样器，并且我们使用高维扩展器证明其存在。
我们展示了双重采样器如何以一种可以有效列表编码的方式给出扩增距离的通用方法。有许多错误纠正代码构造，可以从具有中等距离的基本代码$ c $开始实现较大距离，然后使用采样器（例如ABNNR代码构建[IEEE Trans）扩增距离。通知。理论，38（2）：509--516，1992。]。我们表明，如果采样器是较大的双采样器的一部分，那么构造具有有效的列表编码算法，并且列表解码算法不理会基本代码$ c $（即，它在$ c $中运行$ c $的独特解码器，黑匣子方式）。
我们的列表编码算法的作品如下：它使用本地投票方案，从中构建了独特的游戏约束图。约束图是一个扩展器，因此我们可以有效地解决独特的游戏。这些解决方案是列表解码器的输出。这是在解码过程中使用独特的游戏算法作为子例程的新颖使用，而不是更常见的情况，在这种情况下，使用独特的游戏来证明硬度结果。
双采样器和高维扩展器类似于其实用程序中的伪界对象，但是它们在组合性质中的随机对象大大超过了随机对象。我们认为，这些对象具有编码理论构造的巨大潜力，并将这项工作视为在这种情况下证明了双采样器的力量。
We develop the notion of "double samplers", first introduced by Dinur and Kaufman [Proc. 58th FOCS, 2017], which are samplers with additional combinatorial properties, and whose existence we prove using high dimensional expanders.
We show how double samplers give a generic way of amplifying distance in a way that enables efficient list-decoding. There are many error correcting code constructions that achieve large distance by starting with a base code $C$ with moderate distance, and then amplifying the distance using a sampler, e.g., the ABNNR code construction [IEEE Trans. Inform. Theory, 38(2):509--516, 1992.]. We show that if the sampler is part of a larger double sampler then the construction has an efficient list-decoding algorithm and the list decoding algorithm is oblivious to the base code $C$ (i.e., it runs the unique decoder for $C$ in a black box way).
Our list-decoding algorithm works as follows: it uses a local voting scheme from which it constructs a unique games constraint graph. The constraint graph is an expander, so we can solve unique games efficiently. These solutions are the output of the list decoder. This is a novel use of a unique games algorithm as a subroutine in a decoding procedure, as opposed to the more common situation in which unique games are used for demonstrating hardness results.
Double samplers and high dimensional expanders are akin to pseudorandom objects in their utility, but they greatly exceed random objects in their combinatorial properties. We believe that these objects hold significant potential for coding theoretic constructions and view this work as demonstrating the power of double samplers in this context.
直和码的列表解码
DOI：
10.1137/1.9781611975994.85
发表时间：
2020
期刊：
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Alev, Vedat Levi;Jeronimo, Fernando Granha;Quintana, Dylan;Srivastava, Shashank;Tulsiani, Madhur
通讯作者：
Tulsiani, Madhur