Renmin University | China
Dr. Kun He is an accomplished computer scientist and currently serves as an Associate Professor at Renmin University of China (since January 2023). His academic journey reflects a strong foundation in theoretical computer science, backed by extensive research experience across leading Chinese institutions. Before joining Renmin University, he worked at the Institute of Computing Technology (ICT), Chinese Academy of Sciences (CAS), first as an Assistant Researcher (2021–2022) and later as an Associate Researcher (2022). He also completed a postdoctoral fellowship at Shenzhen University between 2019 and 2021. Dr. He earned his Ph.D. in Computer Science from ICT, CAS in 2019 under the supervision of Prof. Xiaoming Sun. He also holds a Master’s degree from ICT, CAS and a Bachelor of Engineering in Computer Science from Wuhan University. His research centers on the theory of computing, with particular emphasis on probabilistic methods, sampling algorithms, quantum computing, combinatorial structures, and theoretical machine learning. His work has significantly advanced algorithmic techniques related to the Lovász Local Lemma (LLL), Holant problems, and random constraint satisfaction. Over the years, Dr. He has received numerous prestigious awards recognizing the impact and quality of his research. These include the New Hundred Stars of ICT (2021), the Outstanding Doctoral Dissertation Award of the China Computer Federation (2020), the Special Award for the President of CAS (2019), and the National Scholarship of China (2018). These honors highlight his early and sustained contributions to theoretical computer science. Dr. He has published extensively in top-tier venues such as SODA, STOC, FOCS, ITCS, and Random Structures & Algorithms. His notable works include breakthroughs on the Moser–Tardos algorithm, deterministic counting versions of the Lovász Local Lemma, sampling solutions to random CNF formulas, and quantum extensions of classical combinatorial frameworks. Several of his papers have been widely cited and recognized, including a top-downloaded publication in Random Structures & Algorithms (2020). Recently, his research continues to push theoretical boundaries, with upcoming papers on the phase transition of the Sinkhorn–Knopp algorithm and efficient approximation schemes for Holant problems. Dr. He also actively works on emerging topics involving perfect sampling and permutation constraints within the Lopsided LLL regime, with multiple manuscripts currently under submission. With strong expertise, a prolific publication record, and multiple high-impact contributions, Dr. Kun He stands as a leading figure in modern theoretical computer science.
Featured Publications
He, K., Li, L., Liu, X., Wang, Y., & Xia, M. (2025). Variable version Lovász Local Lemma: A tale of two boundaries. Information and Computation, 105386.
He, K. (2025). Phase transition of the Sinkhorn-Knopp algorithm. arXiv preprint arXiv:2507.09711.
He, K., Li, Z., Qiu, G., & Zhang, C. (2025). FPTAS for Holant problems with log-concave signatures. In Proceedings of the 2025 Annual ACM–SIAM Symposium on Discrete Algorithms (SODA).
He, K., Qiu, G., & Sun, X. (2024). Sampling permutations satisfying constraints within the lopsided local lemma regime. arXiv preprint arXiv:2411.02750.
He, K., Qiu, G., & Sun, X. (2024). Sampling permutations satisfying constraints within and beyond the local lemma regime. arXiv e-prints, arXiv:2411.02750.
He, K., Li, Q., & Sun, X. (2023). Moser-Tardos algorithm: Beyond Shearer’s bound. In Proceedings of the 2023 Annual ACM–SIAM Symposium on Discrete Algorithms (SODA).
He, K., Wang, C., & Yin, Y. (2023). Deterministic counting Lovász Local Lemma beyond linear programming. In Proceedings of the 2023 Annual ACM–SIAM Symposium on Discrete Algorithms (SODA).
He, K., Wu, K., & Yang, K. (2023). Improved bounds for sampling solutions of random CNF formulas. In Proceedings of the 2023 Annual ACM–SIAM Symposium on Discrete Algorithms (SODA).
He, K., Wang, C., & Yin, Y. (2022). Sampling Lovász Local Lemma for general constraint satisfaction solutions in near-linear time. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS).