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 broadly in the intersection of theoretical computer science and probability theory. Recently I have been working topics such as Markov chain mixing, distribution testing, and random matrix theory. 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
Few Single-Qubit Measurements Suffice to Certify Any Quantum State.
Meghal Gupta, William He, Ryan O’Donnell.
Preprint 2025. [arXiv]
Pseudorandom Properties of Random Reversible Circuits.
William Gay, William He, Nicholas Kocurek, Ryan O’Donnell.
CRYPTO 2025. [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]
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 and Spring 2025 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.