I am a second-year Ph.D. student in the Computer Science Department at Carnegie Mellon University where I am fortunate to be co-advised by David Woodruff and Richard Peng. Previously, I was an undergraduate at Rutgers University where I was fortunate to be advised by Sepehr Assadi. I also had the privilege of interning with Ching-An Cheng at Microsoft Research in the summer of 2022. I am partially supported by a NSF Graduate Research Fellowship.

My research interests lie in theoretical computer science. In particular, I am thinking about:
- sublinear algorithms (streaming, sketching, sublinear-time)
- communication complexity (for streaming lower bounds)
- graph algorithms (graph sparsification, linear system solving)

I am also passionate about teaching and increasing diversity within CS. I have been a head LA, LA, and TA for various CS courses.

Email: hnnguyen(at)andrew.cmu.edu, CV

Publications

(As is by convention, in theoretical computer science, authors are listed in alphabetical order.)

Maximum Coverage in Turnstile Streams with Applications to Fingerprinting Measures
Alina Ene, Alessandro Epasto, Vahab Mirrokni, Hoai-An Nguyen, Huy L. Nguyen, David P. Woodruff, Peilin Zhong
ICML 2025
Full Version

Relative Error Fair Clustering in the Weak-Strong Oracle Model
Vladimir Braverman, Prathamesh Dharangutte, Shaofeng Jiang, Hoai-An Nguyen, Chen Wang, Yubo Zhang, Samson Zhou
ICML 2025

Provable Reset-free Reinforcement Learning by No-Regret Reduction
Hoai-An Nguyen, Ching-An Cheng
ICML 2023
Conference Version | Full Version

Asymptotically Optimal Bounds for Estimating H-Index in Sublinear Time with Applications to Subgraph Counting
Sepehr Assadi, Hoai-An Nguyen
APPROX 2022
Conference Version | Full Version | Presentation

Workshop Papers
Provable Reset-free Reinforcement Learning by No-Regret Reduction
Hoai-An Nguyen, Ching-An Cheng
AAAI 2023 RL4PROD Workshop (spotlight)
Paper under the same name published through ICML 2023

Teaching

• TA for Algorithms for Big Data (15-851) @ CMU, Spring 2025
• TA for Algorithm Design and Analysis (15-451) @ CMU, Spring 2024
• TA for Design and Analysis of Computer Algorithms (198-344) @ Rutgers, Spring 2022, Spring 2023
• Head LA for Data Structures (198-112) @ Rutgers, Spring 2021, Fall 2021, Spring 2022
• LA for Data Structures (198-112) @ Rutgers, Spring 2021, Fall 2021, Spring 2022, Fall 2022, Spring 2023
• LA for Introduction to Computer Science (198-111) @ Rutgers, Fall 2020

Service

• reviewer for: ICALP 2024, KDD 2024, STACS 2025
• organized CMU’s algorithms and complexity lunch seminar Spring 2024 - Fall 2024
• session leader for the CMU TechNights program in Fall 2023