Synchronization strings: explicit constructions, local decoding, and applications
Synchronization strings: explicit constructions, local decoding, and applications
复制标题
同步字符串：显式构造、本地解码和应用
DOI：
10.1145/3188745.3188940
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Shahrasbi, Amirbehshad
中科院分区：
文献类型：
--
作者：
Haeupler, Bernhard;Shahrasbi, Amirbehshad
本文给出了同步字符串的新结果，同步字符串是 [Haeupler，Shahrasbi； STOC'17]允许有效地处理各种通信问题中的插入和删除：-我们给出了确定性的线性时间同步字符串构造，改进了 O(n5) 时间随机构造。独立于这项工作，Cheng、Li 和 Wu 提出了确定性的 O(nlog2logn) 时间构造。-我们给出了无限同步串的确定性构造，该同步串在 O(n) 时间内输出第一个 n 个符号。以前不知道这样的字符串是否可计算。- 两种同步字符串构造都是高度明确的，即第一个符号可以在 O(logi) 时间内确定性地计算。- 本文还介绍了一个我们称为长距离同步字符串的广义概念。此类字符串允许本地且非常快速的解码。特别是，解码任何索引只需要 O(log3n) 时间和访问对数数量的符号。本文还为这些改进的同步字符串提供了几种应用： - 对于任何 δ < 1 和 є > 0，我们提供速率为 1 − δ − є 的 insdel 纠错块码，它可以在 O(nlog3n) 时间内纠正插入和删除错误的任何 δ/3 部分。这种接近线性的计算效率是令人惊讶的，因为我们甚至不知道如何在次二次时间内计算解码输入和输出之间的（编辑）距离。-我们表明，局部可解码性意味着用长距离同步字符串构造的纠错码不仅可以有效地从插入错误的δ分数中恢复，而且类似于[Schulman，Zuckerman； TransInf'99]，也来自块转置和块复制的任意 O(δ / logn) 部分。这些块损坏允许任意长的子串在任何地方交换或复制。-我们表明，高度显式和本地解码允许无限通道模拟，而内存和解码时间要求呈指数级减小。然后，这些模拟可用于给出用于插入错误的第一个近线性时间交互式编码方案，类似于[Brakerski，Naor； SODA’13] 用于汉明错误。
This paper gives new results for synchronization strings, a powerful combinatorial object introduced by [Haeupler, Shahrasbi; STOC’17] that allows to efficiently deal with insertions and deletions in various communication problems:- We give a deterministic, linear time synchronization string construction, improving over anO(n5) time randomized construction. Independently of this work, a deterministicO(nlog2logn) time construction was proposed by Cheng, Li, and Wu.- We give a deterministic construction of an infinite synchronization string which outputs the firstnsymbols inO(n) time. Previously it was not known whether such a string was computable.- Both synchronization string constructions are highly explicit, i.e., theith symbol can be deterministically computed inO(logi) time.- This paper also introduces a generalized notion we call long-distance synchronization strings. Such strings allow for local and very fast decoding. In particular onlyO(log3n) time and access to logarithmically many symbols is required to decode any index.The paper also provides several applications for these improved synchronization strings:- For any δ < 1 and є > 0 we provide an insdel error correcting block code with rate 1 − δ − є which can correct any δ/3 fraction of insertion and deletion errors inO(nlog3n) time. This near linear computational efficiency is surprising given that we do not even know how to compute the (edit) distance between the decoding input and output in sub-quadratic time.- We show that local decodability implies that error correcting codes constructed with long-distance synchronization strings can not only efficiently recover from δ fraction of insdel errors but, similar to [Schulman, Zuckerman; TransInf’99], also from anyO(δ / logn) fraction of block transpositions and block replications. These block corruptions allow arbitrarily long substrings to be swapped or replicated anywhere.- We show that highly explicitness and local decoding allow for infinite channel simulations with exponentially smaller memory and decoding time requirements. These simulations can then be used to give the first near linear time interactive coding scheme for insdel errors, similar to the result of [Brakerski, Naor; SODA’13] for Hamming errors.
登录
查看更多内容
针对对抗性噪声的高效交互式编码
DOI：
--
发表时间：
2012
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Zvika Brakerski;Y. Kalai
通讯作者：
Y. Kalai
适用于高噪声和高速率状态的有效可解码插入/删除代码
DOI：
10.1109/isit.2016.7541373
发表时间：
2016
期刊：
2016 IEEE International Symposium on Information Theory (ISIT)
影响因子：
--
作者：
V. Guruswami;Ray Li
通讯作者：
Ray Li
Lovasz局部引理的应用：存在不包含几乎相同区间的无限01序列
DOI：
--
发表时间：
1984
期刊：
影响因子：
--
作者：
J. Beck
通讯作者：
J. Beck
DOI：
--
发表时间：
2017
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Alexander A. Sherstov;Pei Wu
通讯作者：
Pei Wu
DOI：
10.1109/focs.2017.27
发表时间：
2017
期刊：
58th Annual IEEE Symposium on Foundations of Computer Science
影响因子：
--
作者：
Hemenway, Brett;Ron-Zewi, Noga;Wootters, Mary
通讯作者：
Wootters, Mary