9 citations · 15 across the 2 of their papers we have counts for
3 papers
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.IT2020★ 6 cited
Locally Decodable Codes with Randomized Encoding
Kuan Cheng, Xin Li, Yu Zheng
We initiate a study of locally decodable codes with randomized encoding. Standard locally decodable codes are error correcting codes with a deterministic encoding function and a ra…
cs.IT2017★ 9 cited
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…