Kuan Cheng ( 程 宽 )

I am an Assistant Professor at Peking University, Center on Frontiers of Computing Studies (CFCS).

My research interests include Computational Models and Complexity Theory, Pseudorandomness and Coding Theory.

I'm also interested in Machine Learning, Quantum Computing and other topics in Computer Science.

Email: ckkcdh at hotmail/gmail/pku email.

Office: 206-3, Courtyard No. 5, Jingyuan. (In Office every Tuesday 2pm-5pm)

I'm looking for talent students interested in TCS and related areas such as Machine Learning and Quantum Computing! Please feel free to contact me.

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.

Publications

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

Improved Decoding of Expander Codes.

In Innovations in Theoretical Computer Science (ITCS) 2022.


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.