ckkcdh
Room 206-3, Courtyard No.5 Jingyuan
Computational Models and Complexity, Randomness in Computation, Coding Theory, Machine Learning https://ckkcdh.github.io/Bio-Sketch
Dr. Kuan Cheng joined Peking University in August 2020 and is currently an assistant professor at Center on Frontiers of Computing Studies, PKU. Previously he was a postdoc at University of Texas at Austin. He received his PhD in computer science from Johns Hopkins University in 2019. Before that he received his master degree in Tsinghua University and bachelor degree in Shandong University. His research interests mainly include computational models and complexity, pseudorandomness and coding. He is also interested in learning theory and networks. He has published many papers in top conferences of theoretical computer science such as FOCS, CCC, SODA, ICALP, TCC, etc. Major work of him focus on coding for edit distance and hamming distance, also derandomization for circuits and small space computation. He plans to further study these areas in the future, and also extends these results to other popular areas such as machine learning, quantum computation etc.
Know more about Dr. Kuan Cheng: https://sites.google.com/site/ckkcdh/home
Publications
For latest publications, please visit: https://ckkcdh.github.io/
- 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.