1 citations · 1 across the 14 of their papers we have counts for
16 papers · 1 filter
Nearly Optimal Strong Coresets for Subspace Approximation
Honghao Lin, Vahab Mirrokni, David P. Woodruff
We study strong coresets for subspace approximation. Given a matrix , the goal is to sample and rescale a small number of its rows to obtain $S…
A Near-Optimal Lower Bound for Prefix-Matrix Factorizations
Honghao Lin, Vahab Mirrokni, David P. Woodruff
For the lower-triangular all-ones matrix , we prove a near-optimal lower bound \[ γ_{2,1}(Q) := \inf_{Q=AB} \|A\|_{2\to\infty}\|B\|_{1\to1} = Ω\!\left( \frac{\log^{3…
Pairwise-Independent Dithering for Single-Stage Hadamard Quantization
Honghao Lin, Vahab Mirrokni, David P. Woodruff
Quantizing high-dimensional vectors is fundamental to similarity search, distributed learning, and model compression. Feng, Indyk, Kapralov, Krachun, and Prokhorov established shar…
The Condition-Number Barrier in Sparse Least Squares
Honghao Lin, Vahab Mirrokni, David P. Woodruff
In [AS21], Axiotis and Sviridenko conjectured that the linear dependence on the restricted condition number in sparse convex optimization cannot be improved by a polynomial-time al…
Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity
Rajesh Jayaram, Honghao Lin, Vahab Mirrokni +1
Multi-vector embeddings represent items by point clouds and compare query and document point clouds using Chamfer similarity, whereas single-vector embeddings use ordinary inner pr…
Adversarial Robustness for Small Frequency Moments and a Weak Equivalence Theorem for Turnstile Streams
Elena Gribelyuk, Honghao Lin, David P. Woodruff +2
We study adversarially robust algorithms for insertion-deletion (turnstile) streams, where future updates may depend on past algorithm outputs. While recent work achieved a robust…