5 papers
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…
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…
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…
Optimal Key Consensus in Presence of Noise
Zhengzhong Jin, Yunlei Zhao
In this work, we abstract some key ingredients in previous LWE- and RLWE-based key exchange protocols, by introducing and formalizing the building tool, referred to as key consensu…