程宽
简介
程宽博士，现任北京大学前沿计算研究中心助理教授，博士生导师，于2020年8月正式加入中心。他于2011年和2014年分别在山东大学和清华大学获学士、硕士学位，于2019年在约翰· 霍普金斯大学获博士学位，之后在德克萨斯大学奥斯汀分校进行博士后研究。研究兴趣包括计算模型与复杂性、伪随机与编码、机器学习、网络协议等。截至2020年7月，程宽博士的多篇论文发表于FOCS, CCC, SODA, ICALP, TCC等理论计算机领域的顶级会议中。已有的主要工作专注于针对汉明距离和编辑距离的编码，以及针对电路和小空间计算模型的去随机化。程宽博士计划在将来继续深入研究这些领域，并且将研究拓展至其它热门领域，如机器学习、量子计算等。
发表论著
最新发表情况请见个人网站：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.