William He
About Me
Welcome to my website! I am a second-year Ph.D. student in the Computer Science Department at Carnegie Mellon University. I am fortunate to be advised by Ryan O’Donnell. Previously, I was an undergraduate at Duke University, where I got my B.S. in Mathematics and Computer Science and was fortunate to be advised by Benjamin Rossman and Debmalya Panigrahi.
My research interests lie in theoretical computer science. Recently I have been thinking about problems in pseudorandomness and Markov chain mixing. As an undergraduate I worked on circuit complexity and graph algorithms.
Outside of research, I enjoy playing basketball, playing tennis, and watching movies.
My email: william.rui.he “at” gmail.com or wrhe “at” cs.cmu.edu
Publications
Faster Mixing of Higher-Dimensional Random Reversible Circuits.
William Gay, William He, Nicholas Kocurek.
Preprint. [arXiv]
More Efficient Approximate k-wise Independent Permutations from Random Reversible Circuits via log-Sobolev Inequalities.
Lucas Gretta, William He, Angelos Pelecanos.
SODA 2025. [arXiv]
Pseudorandom Permutations from Random Reversible Circuits.
William He, Ryan O’Donnell.
Preprint. [arXiv]
Testing Junta Truncation.
William He, Shivam Nadimpalli.
Preprint. [arXiv]
Beyond the Quadratic Time Barrier for Network Unreliability.
Ruoxu Cen, William He, Jason Li, Debmalya Panigrahi.
SODA 2024. [arXiv]
Steiner Connectivity Augmentation and Splitting-off in Poly-logarithmic Maximum Flows.
Ruoxu Cen, William He, Jason Li, Debmalya Panigrahi.
SODA 2023. [arXiv]
Symmetric Formulas for Products of Permutations.
William He, Benjamin Rossman.
ITCS 2023. [arXiv]
Teaching
- In Spring 2024 I was a TA for 15-751 (CS Theory Toolkit).
Other
- In Fall 2024 I am a co-organizer of CMU’s Theory Lunch.
- Reviewer for: ESA 2024.
- In Fall 2023 I co-organized a reading group on high-dimensional expanders.
- In Fall 2023 I was a Session Leader for the CMU TechNights program.