9 citations · 15 across the 4 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2020
Space Efficient Deterministic Approximation of String Measures
Kuan Cheng, Zhengzhong Jin, Xin Li +1
We study approximation algorithms for the following three string measures that are widely used in practice: edit distance (ED), longest common subsequence (LCS), and longest increa…
cs.DS2018
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…
cs.DS2018
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…