Hoai-An Nguyen

collaborators

3 papers

cs.DS2026

Streaming Complexity Separations for Dense and Sparse Graphs

Yang P. Liu, Hoai-An Nguyen, Noah G. Singer +1

We identify a sharp separation in the streaming space complexity of Maximum Cut when the algorithm must output an approximate cut (rather than only the approximate value). For dens…

cs.DS2025

Unbiased Insights: Optimal Streaming Algorithms for $ℓ_{p}$ Sampling, the Forget Model, and Beyond

Honghao Lin, Hoai-An Nguyen, William Swartworth +1

We study $ℓ_{p}$ sampling and frequency moment estimation in a single-pass insertion-only data stream. For $p \in (0, 2)$ , we present a nearly space-optimal approximate $ℓ_{p}$ sa…

cs.DS2025

On Sketching Trimmed Statistics

Honghao Lin, Hoai-An Nguyen, David P. Woodruff

We study sketching trimmed statistics of a frequency vector, including the $F_{p}$ moment of the top- $k$ coordinates and of the trimmed- $k$ vector. Despite their natural role in robu…

Streaming Complexity Separations for Dense and Sparse Graphs

Unbiased Insights: Optimal Streaming Algorithms for ℓp​ Sampling, the Forget Model, and Beyond

On Sketching Trimmed Statistics

Unbiased Insights: Optimal Streaming Algorithms for $ℓ_{p}$ Sampling, the Forget Model, and Beyond