Error Correcting Codes that Achieve BSC Capacity Against Channels that are Poly-Size Circuits
Error Correcting Codes that Achieve BSC Capacity Against Channels that are Poly-Size Circuits
复制标题
针对多尺寸电路通道实现 BSC 容量的纠错码
DOI：
10.1109/focs54457.2022.00009
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Jad Silbak
中科院分区：
文献类型：
--
作者：
Ronen Shaltiel;Jad Silbak
Guruswami和Smith（J. ACM 2016）考虑了用于多尺寸电路的信道的代码，这些电路最多修改码字的p部分比特。这类信道明显强于Shannon的二进制对称信道（BSC），但弱于Hamming的计算无界信道。Guruswami和Smith给出了一个显式的蒙特-卡罗码构造，其最佳速率为R（p）= 1 − H（p），在这种情况下实现了列表解码。这里，“显式蒙特-卡罗”意味着编码和解码算法都在多项式时间内运行。然而，编码和解码算法还接收多项式长度的均匀选择的串（其在预处理阶段中被选择和发布，一劳永逸），并且它们的正确性在该随机选择上得到保证。Guruswami和Smith提出了一个问题，即是否有可能获得多尺寸信道的唯一可解码码，其速率超过Gilbert-Varshamov界$R^{GV}（p）=1-H（2 p）$。我们给出了一个肯定的答案，具体地说：·对于每$0\leq p\lt\frac{1}{4}$，我们给出了一个显式的蒙特-卡罗构造的可解码码的最佳速率R（p）= 1 − H（p）。这与Guruswami和Smith为更容易的列表解码任务所实现的速率相匹配，并且也与二进制对称信道的容量相匹配。此外，该速率严格大于标准编码场景中的码（即，汉明信道的可解码码）。·即使忽略显式性，我们的结果意味着一个表征的容量多尺寸的信道，这是以前没有understood.我们的技术建立在早期的列表可解码的代码Guruswami和史密斯，实现唯一的解码，通过扩展和修改的建设，使我们可以识别正确的消息列表中。·我们为二进制对称信道构造代码，这些代码超过Gilbert-Varshamov界限，并且在接收随机（或实际上伪随机）字符串的多尺寸电路无法在相对距离2 p内找到码字的意义上是“回避的”。这种回避的概念受到Shaltiel和Silbak（STOC 2021）最近关于空间有界信道编码的工作的启发。·我们开发了一种方法（该方法的灵感来自于t方向独立尾不等式的证明，并且可能具有独立的兴趣）来分析随机码，在这种情况下，信道的成功是在额外的随机实验中测量的（如上面的逃避实验）。·我们引入了一个新的概念，“小集不可延展的代码”，是为我们的应用程序量身定制的，可能是独立的利益。
Guruswami and Smith (J. ACM 2016) considered codes for channels that are poly-size circuits which modify at most a p-fraction of the bits of the codeword. This class of channels is significantly stronger than Shannon’s binary symmetric channel (BSC), but weaker than Hamming’s channels which are computationally unbounded. Guruswami and Smith gave an explicit Monte-Carlo construction of codes with optimal rate of R(p) = 1 − H(p) that achieve list-decoding in this scenario. Here, “explicit Monte-Carlo” means that both encoding and decoding algorithms run in polynomial time. However, the encoding and decoding algorithms also receive a uniformly chosen string of polynomial length (which is chosen and published, once and for all, in a pre-processing stage) and their correctness is guaranteed w.h.p. over this random choice. Guruswami and Smith asked whether it is possible to obtain uniquely decodable codes for poly-size channels with rate that beats the Gilbert-Varshamov bound $R^{GV}(p)=1-H(2p)$. We give an affirmative answer, Specifically:•For every $0\leq p\lt\frac{1}{4}$, we give an explicit Monte-Carlo construction of uniquely-decodable codes with optimal rate R(p) = 1 − H(p). This matches the rate achieved by Guruswami and Smith for the easier task of list-decoding, and also matches the capacity of binary symmetric channels. Moreover, this rate is strictly larger than that of codes for the standard coding scenario (namely, uniquely-decodable codes for Hamming channels).•Even ignoring explicitness, our result implies a characterization of the capacity of poly-size channels, which was not previously understood.Our technique builds on the earlier list-decodable codes of Guruswami and Smith, achieving unique-decoding by extending and modifying the construction so that we can identify the correct message in the list. For this purpose we use ideas from coding theory and pseudorandomness, specifically:•We construct codes for binary symmetric channels that beat the Gilbert-Varshamov bound, and are “evasive” in the sense that a poly-size circuit that receives a random (or actually pseudorandom) string, cannot find a codeword within relative distance 2p. This notion of evasiveness is inspired by the recent work of Shaltiel and Silbak (STOC 2021) on codes for space bounded channels.•We develop a methodology (that is inspired by proofs of t-wise independent tail inequalities, and may be of independent interest) to analyze random codes, in scenarios where the success of the channel is measured in an additional random experiment (as in the evasiveness experiment above).•We introduce a new notion of “small-set non-malleable codes” that is tailored for our application, and may be of independent interest.
通过可分割正则性对 Ta-Shma 码进行近线性时间解码
DOI：
10.1145/3406325.3451126
发表时间：
2021
期刊：
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Jeronimo, Fernando Granha;Srivastava, Shashank;Tulsiani, Madhur
通讯作者：
Tulsiani, Madhur
影响因子：
2.5
作者：
Guruswami, Venkatesan;Smith, Adam
通讯作者：
Smith, Adam