Explicit, almost optimal, epsilon-balanced codes
Explicit, almost optimal, epsilon-balanced codes
复制标题
显式的、几乎最优的、epsilon 平衡的代码
DOI：
10.1145/3055399.3055408
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
A. Ta
中科院分区：
文献类型：
--
作者：
A. Ta
寻找具有接近最优支撑大小的\(\epsilon\)-偏置集，或者等价地，寻找距离为\(1 - \frac{\epsilon}{2}\)且码率接近吉尔伯特 - 瓦尔沙莫夫界的显式二进制码，这一问题在近几十年引起了大量关注。在本文中，我们几乎最优地解决了该问题，并展示了一个在\(k\)位上的显式\(\epsilon\)-偏置集，其支撑大小为\(O(\frac{k}{\epsilon^{2 + o(1)}})\)。这改进了之前所有显式构造，之前的构造量级为\(\frac{k^{2}}{\epsilon^{2}}\)、\(\frac{k}{\epsilon^{3}}\)或\(\frac{k^{\frac{5}{4}}}{\epsilon^{\frac{5}{2}}}\)。该结果接近吉尔伯特 - 瓦尔沙莫夫界\(O(\frac{k}{\epsilon^{2}})\)以及下界\(\Omega(\frac{k}{\epsilon^{2}}\log^{\frac{1}{\epsilon}})\)。我们使用的主要技术工具是通过\(s\)-宽替换积进行偏置放大。从一个\(\epsilon\)-偏置集中选取两个独立样本，其和是\(\epsilon^{2}\)-偏置的。罗森曼和威格森展示了如何通过在扩展图上选择两个样本更经济地放大偏置。基于此，他们提出了一种递归构造，实现了样本大小为\(O(\frac{k}{\epsilon^{4}})\)。我们表明，通过在\(s\)-宽替换积上进行长随机游走进行放大几乎最优地降低了偏置。
The question of finding an epsilon-biased set with close to optimal support size, or, equivalently, finding an explicit binary code with distance 1-ϵ/2 and rate close to the Gilbert-Varshamov bound, attracted a lot of attention in recent decades. In this paper we solve the problem almost optimally and show an explicit ϵ-biased set over k bits with support size O(k/ϵ2+o(1)). This improves upon all previous explicit constructions which were in the order of k2/ϵ2, k/ϵ3 or k5/4/ϵ5/2. The result is close to the Gilbert-Varshamov bound which is O(k/ϵ2) and the lower bound which is Ω(k/ϵ2 log1/ϵ). The main technical tool we use is bias amplification with the s-wide replacement product. The sum of two independent samples from an ϵ-biased set is ϵ2 biased. Rozenman and Wigderson showed how to amplify the bias more economically by choosing two samples with an expander. Based on that they suggested a recursive construction that achieves sample size O(k/ϵ4). We show that amplification with a long random walk over the s-wide replacement product reduces the bias almost optimally.