9 citations · 11 across the 3 of their papers we have counts for
5 papers
Beyond Single-Deletion Correcting Codes: Substitutions and Transpositions
Ryan Gabrys, Venkatesan Guruswami, João Ribeiro +1
We consider the problem of designing low-redundancy codes in settings where one must correct deletions in conjunction with substitutions or adjacent transpositions; a combination o…
Block Edit Errors with Transpositions: Deterministic Document Exchange Protocols and Almost Optimal Binary Codes
Kuan Cheng, Zhengzhong Jin, Xin Li +1
Document exchange and error correcting codes are two fundamental problems regarding communications. In the first problem, Alice and Bob each holds a string, and the goal is for Ali…
Deterministic Document Exchange Protocols, and Almost Optimal Binary Codes for Edit Errors
Kuan Cheng, Zhengzhong Jin, Xin Li +1
We study two basic problems regarding edit error, i.e. document exchange and error correcting codes for edit errors (insdel codes). For message length and edit error upper boun…
Synchronization Strings: Efficient and Fast Deterministic Constructions over Small Alphabets
Kuan Cheng, Bernhard Haeupler, Xin Li +2
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…
Synchronization Strings: Efficient and Fast Deterministic Constructions over Small Alphabets
Kuan Cheng, Xin Li, Ke Wu
Synchronization strings are recently introduced by Haeupler and Shahrasbi [HS17a] in the study of codes for correcting insertion and deletion errors (insdel codes). A synchronizati…