3 citations · 5 across the 21 of their papers we have counts for
Showing 2024Show all
3 papers · 1 filter
cs.DS2024
A Strong Separation for Adversarially Robust Estimation for Linear Sketches
Elena Gribelyuk, Honghao Lin, David P. Woodruff +2
The majority of streaming problems are defined and analyzed in a static setting, where the data stream is any worst-case sequence of insertions and deletions that is fixed in advan…
cs.DS2024
Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms
Yi Li, Honghao Lin, David P. Woodruff
We study the problem of residual error estimation for matrix and vector norms using a linear sketch. Such estimates can be used, for example, to quickly assess how useful a more ex…
cs.DS2024
Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut
Yu Cheng, Max Li, Honghao Lin +3
In this paper, we consider two fundamental cut approximation problems on large graphs. We prove new lower bounds for both problems that are optimal up to logarithmic factors. The f…