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.