Synchronization strings: explicit constructions, local decoding, and applications

DOI10.1145/3188745.3188940zbMATH Open1446.94203arXiv1710.09795OpenAlexW2963700977MaRDI QIDQ5230342FDOQ5230342

Authors: Bernhard Haeupler, Amirbehshad Shahrasbi 

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Abstract: This paper gives new results for synchronization strings, a powerful combinatorial object that allows to efficiently deal with insertions and deletions in various communication settings: $$ We give a deterministic, linear time synchronization string construction, improving over an $O(n^5)$ time randomized construction. Independently of this work, a deterministic $O(nlo{g}^{2}logn)$ time construction was just put on arXiv by Cheng, Li, and Wu. We also give a deterministic linear time construction of an infinite synchronization string, which was not known to be computable before. Both constructions are highly explicit, i.e., the $i^{th}$ symbol can be computed in $O(logi)$ time. $$ This paper also introduces a generalized notion we call long-distance synchronization strings that allow for local and very fast decoding. In particular, only $O(lo{g}^{3}n)$ time and access to logarithmically many symbols is required to decode any index. We give several applications for these results: $$ For any $delta<1$ and $epsilon>0$ we provide an insdel correcting code with rate $1-delta-epsilon$ which can correct any $O(delta)$ fraction of insdel errors in $O(nlo{g}^{3}n)$ 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 such codes can not only efficiently recover from $delta$ fraction of insdel errors but, similar to [Schulman, Zuckerman; TransInf'99], also from any $O(delta/logn)$ fraction of block transpositions and replications. $$ We show that highly explicitness and local decoding allow for infinite channel simulations with exponentially smaller memory and decoding time requirements. These simulations can be used to give the first near linear time interactive coding scheme for insdel errors.

Full work available at URL: https://arxiv.org/abs/1710.09795

Recommendations

• Synchronization strings: channel simulations and interactive coding for insertions and deletions
• Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound
• Synchronization strings: codes for insertions and deletions approaching the Singleton bound
• Synchronization strings: highly efficient deterministic constructions over small alphabets
• Synchronization strings: list decoding for insertions and deletions

zbMATH Keywords

insertions and deletionssynchronization strings

Mathematics Subject Classification ID

Decoding (94B35)

Cited In (13)

• Memory-hard puzzles in the standard model with applications to memory-hard functions and resource-bounded locally decodable codes
• Shortest synchronizing strings for Huffman codes
• Efficient Linear and Affine Codes for Correcting Insertions/Deletions
• Title not available (Why is that?)
• Synchronization strings: codes for insertions and deletions approaching the Singleton bound
• Synchronization strings: highly efficient deterministic constructions over small alphabets
• New dimension-independent upper bounds on linear insdel codes
• Synchronization strings: list decoding for insertions and deletions
• Synchronization strings: channel simulations and interactive coding for insertions and deletions
• On 2-dimensional insertion-deletion Reed-Solomon codes with optimal asymptotic error-correcting capability
• Near-linear time insertion-deletion codes and \((1+\varepsilon)\)-approximating edit distance via indexing
• Deterministic document exchange protocols and almost optimal binary codes for edit errors
• Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound

This page was built for publication: Synchronization strings: explicit constructions, local decoding, and applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5230342)