9 citations · 22 across the 11 of their papers we have counts for
4 papers · 1 filter
Efficient Linear and Affine Codes for Correcting Insertions/Deletions
Kuan Cheng, Venkatesan Guruswami, Bernhard Haeupler +1
This paper studies \emph{linear} and \emph{affine} error-correcting codes for correcting synchronization errors such as insertions and deletions. We call such codes linear/affine i…
Efficient Document Exchange and Error Correcting Codes with Asymmetric Information
Kuan Cheng, Xin Li
We study two fundamental problems in communication, Document Exchange (DE) and Error Correcting Code (ECC). In the first problem, two parties hold two strings, and one party tries…
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…
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…