10 papers
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…
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…
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…
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…
On Sketching Trimmed Statistics
Honghao Lin, Hoai-An Nguyen, David P. Woodruff
We study sketching trimmed statistics of a frequency vector, including the moment of the top- coordinates and of the trimmed- vector. Despite their natural role in robu…