Synchronization strings: highly efficient deterministic constructions over small alphabets

DOI10.1137/1.9781611975482.132MaRDI QIDQ5236319zbMATH OpenOpenAlexFDO

Authors Kuan Cheng, Bernhard Haeupler, Amirbehshad Shahrasbi, Ke Wu, Xin Li

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Algorithms on strings (68W32) Synchronization error-correcting codes (94B50)

Abstract: Synchronization strings are recently introduced by Haeupler and Shahrasbi (STOC 2017) in the study of codes for correcting insertion and deletion errors (insdel codes). They showed that for any parameter $varepsilon>0$, synchronization strings of arbitrary length exist over an alphabet whose size depends only on $varepsilon$. Specifically, they obtained an alphabet size of $O(varepsilo{n}^{-4})$, which left an open question on where the minimal size of such alphabets lies between $Omega(varepsilo{n}^{-1})$ and $O(varepsilo{n}^{-4})$. In this work, we partially bridge this gap by providing an improved lower bound of $Omega(varepsilo{n}^{-3/2})$, and an improved upper bound of $O(varepsilo{n}^{-2})$. We also provide fast explicit constructions of synchronization strings over small alphabets. Further, along the lines of previous work on similar combinatorial objects, we study the extremal question of the smallest possible alphabet size over which synchronization strings can exist for some constant $varepsilon<1$. We show that one can construct $varepsilon$-synchronization strings over alphabets of size four while no such string exists over binary alphabets. This reduces the extremal question to whether synchronization strings exist over ternary alphabets.

Recommendations

• Synchronization strings: explicit constructions, local decoding, and applications
• Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound
• Synchronization strings: codes for insertions and deletions approaching the Singleton bound
• Synchronization strings: list decoding for insertions and deletions
• Synchronization strings: channel simulations and interactive coding for insertions and deletions

Cited in

(10)

• scientific article; zbMATH DE number 1927561 (Why is no real title available?)
• Synchronization strings: codes for insertions and deletions approaching the Singleton bound
• Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound
• Synchronization strings: explicit constructions, local decoding, and applications
• Insdel codes from subspace and rank-metric codes
• scientific article; zbMATH DE number 7758340 (Why is no real title available?)
• Memory-hard puzzles in the standard model with applications to memory-hard functions and resource-bounded locally decodable codes
• Efficient Linear and Affine Codes for Correcting Insertions/Deletions
• Deterministic document exchange protocols and almost optimal binary codes for edit errors
• Shortest synchronizing strings for Huffman codes

This page was built for publication: Synchronization strings: highly efficient deterministic constructions over small alphabets

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