Hoai-An

Hoai-An Nguyen

I am a third-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 Yang Liu. 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), and graph algorithms (graph sparsification, linear system solving).

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

Preprints

On Sketching Trimmed Statistics
with Honghao Lin and David P. Woodruff
Full version

Unbiased Insights: Optimal Streaming Algorithms for Lp Sampling, the Forget Model, and Beyond
with Honghao Lin, William Swartworth, and David P. Woodruff
Full version

Publications

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

Numerical Linear Algebra in Linear Space
with Yiping Liu and Junzhao Yang
SODA 2026
Full version

Entrywise Approximation for Matrix Inversion and Linear Systems
with Mehrdad Ghadiri and Junzhao Yang
SODA 2026

Maximum Coverage in Turnstile Streams with Applications to Fingerprinting Measures
with Alina Ene, Alessandro Epasto, Vahab Mirrokni, Huy L. Nguyen, David P. Woodruff, and Peilin Zhong
ICML 2025
Full version | Presentation

Relative Error Fair Clustering in the Weak-Strong Oracle Model
with Vladimir Braverman, Prathamesh Dharangutte, Shaofeng Jiang, Chen Wang, Yubo Zhang, and Samson Zhou
ICML 2025
Full version

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
with Sepehr Assadi
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

Service