Arrow Research search

Author name cluster

Ke Wu 0001

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers
1 author row

Possible papers

2

SODA Conference 2019 Conference Paper

Synchronization Strings: Highly Efficient Deterministic Constructions over Small Alphabets

  • Kuan Cheng
  • Bernhard Haeupler
  • Xin Li 0006
  • Amirbehshad Shahrasbi
  • Ke Wu 0001

Synchronization strings are recently introduced by Haeupler and Shahrasbi [1] in the study of codes for correcting insertion and deletion errors (insdel codes). A synchronization string is an encoding of the indices of the symbols in a string, and together with an appropriate decoding algorithm it can transform insertion and deletion errors into standard symbol erasures and corruptions. This reduces the problem of constructing insdel codes to the problem of constructing standard error correcting codes, which is much better understood. Besides this, synchronization strings are also useful in other applications such as synchronization sequences and interactive coding schemes. For all such applications, synchronization strings are desired to be over alphabets that are as small as possible, since a larger alphabet size corresponds to more redundant information added. Haeupler and Shahrasbi [1] showed that for any parameter ε > 0, synchronization strings of arbitrary length exist over an alphabet whose size depends only on ε. Specifically, [1] obtained an alphabet size of O ( ε −4 ), which left an open question on where the minimal size of such alphabets lies between Ω( ε −1 ) and O ( ε −4 ). In this work, we partially bridge this gap by providing an improved lower bound of Ω ( ε −3/2 ), and an improved upper bound of O ( ε −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 ε < 1. We show that one can construct ε-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.

Details

FOCS Conference 2018 Conference Paper

Deterministic Document Exchange Protocols, and Almost Optimal Binary Codes for Edit Errors

  • Kuan Cheng
  • Zhengzhong Jin
  • Xin Li 0006
  • Ke Wu 0001

We study two basic problems regarding edit errors (insertions and deletions). The first one is document exchange, where two parties Alice and Bob hold two strings x and y with a bounded edit distance k. The goal is to have Alice send a short sketch to Bob, so that Bob can recover x based on y and the sketch. The second one is the fundamental problem of designing error correcting codes for edit errors, where the goal is to construct an explicit code to transmit a message x through a channel that can add at most k worst case insertions and deletions, so that the original message x can be successfully recovered at the other end of the channel. Both problems have been extensively studied for decades, and in this paper we focus on deterministic document exchange protocols and binary codes for insertions and deletions (insdel codes). If the length of x is n, then it is known that for small k (e. g. , k ≤ n/4), in both problems the optimal sketch size or the optimal number of redundant bits is Θ(k log n/k). In particular, this implies the existence of binary codes that can correct ε fraction of insertions and deletions with rate 1-Θ(ε log (1/ε). However, known constructions are far from achieving these bounds. In this paper we significantly improve previous results on both problems. For document exchange, we give an efficient deterministic protocol with sketch size O(k log 2 n/k). This significantly improves the previous best known deterministic protocol, which has sketch size O(k 2 + k log 2 n) [2]. For binary insdel codes, we obtain the following results: 1) An explicit binary insdel code which encodes an n-bit message x against k errors with redundancy O(k log 2 n/k). In particular this implies an explicit family of binary insdel codes that can correct ε fraction of insertions and deletions with rate 1-O(ε log 2 1/(1-ε))=1-Õ(ε). This significantly improves the previous best known result which only achieves rate 1-Õ(√ε) [11], [10], and is optimal up to a log (1/ε) factor. 1) An explicit binary insdel code which encodes an n-bit message x against k errors with redundancy O(k log n). This significantly improves the previous best known result of [4], which only works for constant k and has redundancy O(k 2 log k log n); and that of [2], which has redundancy O(k 2 + k log 2 n). Our code has optimal redundancy for k ≤ n 1-α, any constant 0 <; α <; 1. This is the first explicit construction of binary insdel codes that has optimal redundancy for a wide range of error parameters k, and this brings our understanding of binary insdel codes much closer to that of standard binary error correcting codes. In obtaining our results we introduce several new techniques. Most notably, we introduce the notion of ε-self matching hash functions and ε-synchronization hash functions. We believe our techniques can have further applications in the literature.

Details
v2026.09.13