6 citations · 6 across the 4 of their papers we have counts for
7 papers
Streaming and Query Once Space Complexity of Longest Increasing Subsequence
Xin Li, Yu Zheng
Longest Increasing Subsequence (LIS) is a fundamental problem in combinatorics and computer science. Previously, there have been numerous works on both upper bounds and lower bound…
Linear Insertion Deletion Codes in the High-Noise and High-Rate Regimes
Kuan Cheng, Zhengzhong Jin, Xin Li +2
This work continues the study of linear error correcting codes against adversarial insertion deletion errors (insdel errors). Previously, the work of Cheng, Guruswami, Haeupler, an…
On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors
Alex Block, Jeremiah Blocki, Kuan Cheng +4
Locally Decodable Codes (LDCs) are error-correcting codes with super-fast decoding algorithms. They are important mathematical objects in many areas of theor…
Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions
Jeremiah Blocki, Kuan Cheng, Elena Grigorescu +3
Locally Decodable Codes (LDCs) are error-correcting codes for which individual message symbols can be quickly recovered despite errors in the codeword. LDCs for Hamming errors have…
Lower Bounds and Improved Algorithms for Asymmetric Streaming Edit Distance and Longest Common Subsequence
Xin Li, Yu Zheng
In this paper, we study edit distance (ED) and longest common subsequence (LCS) in the asymmetric streaming model, introduced by Saks and Seshadhri [SS13]. As an intermediate model…
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…