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
77 * 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
35 * 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
26 2023 Hitting Sets Give Two-Sided Derandomization of Small Space. K Cheng, W Hoza
Computational Complexity Conference (CCC) 2020, 2020
25 2020 Randomness extraction in AC0 and with small locality K Cheng, X Li
Approximation, Randomization, and Combinatorial Optimization. Algorithms and …, 2018
23 2018 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
16 2018 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
13 2021 Locally decodable codes with randomized encoding K Cheng, X Li, Y Zheng
arXiv preprint arXiv:2001.03692, 2020
10 2020 Improved decoding of expander codes X Chen, K Cheng, X Li, M Ouyang
IEEE Transactions on Information Theory 69 (6), 3574-3589, 2023
8 2023 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
6 2022 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
5 2021 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
4 2023 Space efficient deterministic approximation of string measures K Cheng, Z Jin, X Li, Y Zheng
arXiv preprint arXiv:2002.08498, 2020
4 2020 On K Cheng, E Grigorescu, X Li, M Sudan, M Zhu
2024 IEEE International Symposium on Information Theory (ISIT), 879-884, 2024
3 2024 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
3 2023 Randomness Extractors in AC 0 and NC: Optimal up to Constant Factors K Cheng, R Wu
Approximation, Randomization, and Combinatorial Optimization. Algorithms and …, 2024
2 2024 Random Shortening of Linear Codes and Applications X Chen, K Cheng, X Li, S Mao
International Computing and Combinatorics Conference, 184-197, 2023
2 2023 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
1 2023 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
1 2023 