Follow
Kuan Cheng
Title
Cited by
Cited by
Year
Deterministic document exchange protocols and almost optimal binary codes for edit errors
K Cheng, Z Jin, X Li, K Wu
Journal of the ACM 69 (6), 1-39, 2022
70*2022
Synchronization strings: Highly efficient deterministic constructions over small alphabets
K Cheng, B Haeupler, X Li, A Shahrasbi, K Wu
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete …, 2019
36*2019
Efficient linear and affine codes for correcting insertions/deletions
K Cheng, V Guruswami, B Haeupler, X Li
SIAM Journal on Discrete Mathematics 37 (2), 748-778, 2023
222023
Hitting Sets Give Two-Sided Derandomization of Small Space.
K Cheng, W Hoza
Computational Complexity Conference (CCC) 2020, 2020
202020
Near-Optimal Secret Sharing and Error Correcting Codes in AC0
K Cheng, Y Ishai, X Li
Theory of Cryptography Conference, 424-458, 2017
20*2017
Block edit errors with transpositions: Deterministic document exchange protocols and almost optimal binary codes
K Cheng, Z Jin, X Li, K Wu
46th International Colloquium on Automata, Languages, and Programming (ICALP …, 2018
172018
Randomness extraction in AC0 and with small locality
K Cheng, X Li
Approximation, Randomization, and Combinatorial Optimization. Algorithms and …, 2018
162018
Efficient document exchange and error correcting codes with asymmetric information
K Cheng, X Li
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA …, 2021
122021
Locally decodable codes with randomized encoding
K Cheng, X Li, Y Zheng
arXiv preprint arXiv:2001.03692, 2020
92020
Improved decoding of expander codes
X Chen, K Cheng, X Li, M Ouyang
IEEE Transactions on Information Theory, 2023
52023
Exponential lower bounds for locally decodable and correctable codes for insertions and deletions
J Blocki, K Cheng, E Grigorescu, X Li, Y Zheng, M Zhu
2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS …, 2022
52022
Streaming and small space approximation algorithms for edit distance and longest common subsequence
K Cheng, A Farhadi, MT Hajiaghayi, Z Jin, X Li, A Rubinstein, S Seddighin, ...
International Colloquium on Automata, Languages, and Programming (ICALP) 2021, 2021
52021
Space efficient deterministic approximation of string measures
K Cheng, Z Jin, X Li, Y Zheng
arXiv preprint arXiv:2002.08498, 2020
42020
Random Shortening of Linear Codes and Applications
X Chen, K Cheng, X Li, S Mao
International Computing and Combinatorics Conference, 184-197, 2023
22023
On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors
AR Block, J Blocki, K Cheng, E Grigorescu, X Li, Y Zheng, M Zhu
38th Computational Complexity Conference (CCC 2023), 2023
22023
On k-Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction
K Cheng, E Grigorescu, X Li, M Sudan, M Zhu
arXiv preprint arXiv:2308.14993, 2023
12023
Linear insertion deletion codes in the high-noise and high-rate regimes
K Cheng, Z Jin, X Li, Z Wei, Y Zheng
arXiv preprint arXiv:2303.17370, 2023
12023
On The Relative Error of Random Fourier Features for Preserving Kernel Distance
K Cheng, SHC Jiang, L Wei, Z Wei
The Eleventh International Conference on Learning Representations (ICLR 2023), 2023
12023
Improved decoding of expander codes: fundamental trade-off between expansion ratio and minimum distance of inner code
K Cheng, M Ouyang, C Shangguan, Y Shen
arXiv preprint arXiv:2312.16087, 2023
2023
Pseudorandom Constructions: Computing in Parallel and Applications to Edit Distance Codes
K Cheng
Johns Hopkins University, 2019
2019
The system can't perform the operation now. Try again later.
Articles 1–20