Skip to content

Author

Hoai-An Nguyen

2 papers indexed here

We haven’t gathered this author’s papers yet. Follow them and we’ll fetch their work.

Not the right person? Other researchers publish under this name.

Preprint Oct 2026

An Unconditional Space-Approximation Lower Bound for Semi-Streaming Matching

We prove the first unconditional lower bound tradeoff between the number of passes and the approximation factor of maximum matchings in the semi-streaming model. Specifically, we show that any algorithm that outputs an $(1-\varepsilon)$-approximation to maximum matching requires $\Omega(\log(1/\varepsilon))$ passes for...

Yang P. Liu, Kheeran K. Naidu, Hoai-An Nguyen et al. · 0 citations
Preprint Oct 2026

A Nearly Optimal Min-Cut Algorithm for Dynamic Streams

We give an $\tilde{O}(n/\varepsilon)$-space algorithm for the minimum cut problem in dynamic streams, resolving the space complexity of streaming min-cut up to polylogarithmic factors. Ding, Garces, Li, Lin, Nelson, Shah, and Woodruff (ITCS 2025) obtained the same $\tilde{O}(n/\varepsilon)$ space bound for insertion-on...

Yang P. Liu, Hoai-An Nguyen, Vihan Shah et al. · 1 citation

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.