William He

About Me
Welcome to my website! I am a first-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, attempting to climb rocks, and watching movies.

My email: william.rui.he “at” gmail.com or wrhe “at” cs.cmu.edu


More Efficient Approximate k-wise Independent Permutations from Random Reversible Circuits via log-Sobolev Inequalities.
Lucas Gretta, William He, Angelos Pelecanos.
Preprint. [ePrint]

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]


  • In Spring 2024 I am a TA for 15-751 (CS Theory Toolkit).


  • 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.