Education

Previously I was a postdoc at The University of Texas at Austin, hosted by David Zuckerman.

I achieved a PhD degree from Johns Hopkins University, Computer Science Department,

advised by Xin Li.

Before that I obtained a master degree from Tsinghua University and a bachelor degree from Shandong University. 

Teaching

Introduction to Theory of Computation, 2021 Spring.

Introduction to Theory of Computation, 2022 Spring. 

Theory of Computation: Advanced Methods and Frontier Topics, 2022 Fall.

Introduction to Theory of Computation, 2023 Spring. 

Publications

Alex Block, Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng, Minshen Zhu;

On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors;

In Computation Complexity Conference (CCC) 2023.

Kuan Cheng, Zhengzhong Jin, Xin Li, Zhide Wei, Yu Zheng;

Linear Insertion Deletion Codes in the High-Noise and High-Rate Regimes;

In International Colloquium on Automata, Languages and Programming (ICALP) 2023.

Kuan Cheng, Shaofeng H.-C. Jiang, Luojian Wei, Zhide Wei;

On The Relative Error of Random Fourier Features for Preserving Kernel Distance;

In International Conference on Learning Representations (ICLR) 2023.

Xue Chen, Kuan Cheng, Xin Li, Minghui Ouyang;

Improved Decoding of Expander Codes;

In IEEE Transaction on Information Theory (IEEE ToIT) 2023.

Kuan Cheng, Zhengzhong Jin, Xin Li, Ke Wu;

Deterministic Document Exchange Protocols and Almost Optimal Binary Codes for Edit Errors;

Journal of the ACM (JACM), Volume 69, Issue 6, December 2022, Article No.: 44, pp 1–39.

Xue Chen, Kuan Cheng, Xin Li, Minghui Ouyang;

Improved Decoding of Expander Codes;

In Innovations in Theoretical Computer Science (ITCS) 2022.

Kuan Cheng, William M. Hoza;

Hitting Sets Give Two-Sided Derandomization of Small Space;

Theory OF Computing 18, no. 21 (2022): 1-32.

Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng and Minshen Zhu;

Exponential Lower Bounds for Locally Decodable Codes Correcting Insertions and Deletions;

In Annual IEEE Symposium on Foundations of Computer Science (FOCS) 2021.

Kuan Cheng, Alireza Farhadi, MohammadTaghi Hajiaghayi, Zhengzhong Jin, Xin Li, Aviad Rubinstein, Saeed Seddighin, Yu Zheng;

Streaming and Small Space Approximation Algorithms for Edit  Distance and Longest Common Subsequence;

In International Colloquium on Automata, Languages and Programming (ICALP) 2021.

Kuan Cheng, Venkatesan Guruswami, Bernhard Haeupler, Xin Li;

Efficient Linear and Affine Codes for Correcting Insertions/Deletions;

In ACM-SIAM Symposium on Discrete Algorithms (SODA) 2021.

Kuan Cheng, Xin Li;

Efficient Document Exchange and Error Correcting Codes with Asymmetric Information;

In ACM-SIAM Symposium on Discrete Algorithms (SODA) 2021.

Kuan Cheng, Zhengzhong Jin, Xin Li, Yu Zheng;

Space Efficient Deterministic Approximation of String Measures;

Arxiv preprint 2020.

Kuan Cheng, William Hoza;

Hitting Sets Give Two-Sided Derandomization of Small Space;

In Computational Complexity Conference (CCC) 2020.

Kuan Cheng, Xin Li, Yu Zheng;

Locally Decodable Codes with Randomized Encoding;

Arxiv preprint 2020.

Kuan Cheng, Zhengzhong Jin, Xin Li, Ke Wu;

Block Edit Errors with Transpositions: Deterministic Document Exchange Protocols and Almost Optimal Binary Codes;

In International Colloquium on Automata, Languages and Programming (ICALP) 2019.

Kuan Cheng, Bernhard Haeupler, Xin Li, Amirbehshad Shahrasbi, Ke Wu;

Synchronization strings: Highly efficient deterministic constructions over small alphabets;

In ACM-SIAM Symposium on Discrete Algorithms (SODA) 2019.

Kuan Cheng, Zhengzhong Jin, Xin Li, Ke Wu;

Deterministic Document Exchange Protocols, and Almost Optimal Binary Codes for Edit Errors;

In Annual IEEE Symposium on Foundations of Computer Science (FOCS) 2018.

Kuan Cheng, Xin Li;

Randomness Extraction in AC0 and with Small Locality;

In International Conference on Randomization and Computation (RANDOM) 2018.

Kuan Cheng, Yuval Ishai, Xin Li;

Near-Optimal Secret Sharing and Error Correcting Codes in AC0;

In Theory of Cryptography Conference (TCC) 2017.