Honghao Lin

activity

20202026

most citedLearning Augmented Binary Search Trees

3 citations · 5 across the 21 of their papers we have counts for

collaborators

24 papers

cs.DS2026

A Proof of the Most Informative Boolean Function Conjecture

Zijie Chen, Amin Gohari, Adel Javanmard +4

Let $X$ be uniform on ${- 1, 1}^{n}$ , let $Y$ be obtained by passing its coordinates independently through a binary symmetric channel with crossover probability $p$ , and let $g:\{-1,…

cs.DS2026

Nearly Optimal Strong Coresets for $ℓ_{p}$ Subspace Approximation

Honghao Lin, Vahab Mirrokni, David P. Woodruff

We study strong coresets for $ℓ_{p}$ subspace approximation. Given a matrix $A \in R^{n \times d}$ , the goal is to sample and rescale a small number of its rows to obtain $S…

cs.DS2026

A Near-Optimal Lower Bound for Prefix-Matrix Factorizations

Honghao Lin, Vahab Mirrokni, David P. Woodruff

For the $n \times n$ lower-triangular all-ones matrix $Q$ , we prove a near-optimal lower bound \[ γ_{2,1}(Q) := \inf_{Q=AB} \|A\|_{2\to\infty}\|B\|_{1\to1} = Ω\!\left( \frac{\log^{3…

cs.DS2026

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…

cs.DS2026

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…

cs.DS2026

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…

cs.DS2026

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…

cs.DS2026

Adversarial Robustness on Insertion-Deletion 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 robust algorithms exist for in…

cs.DS2025

$L_{p}$ Sampling in Distributed Data Streams with Applications to Adversarial Robustness

Honghao Lin, Zhao Song, David P. Woodruff +2

In the distributed monitoring model, a data stream over a universe of size $n$ is distributed over $k$ servers, who must continuously provide certain statistics of the overall data…

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…

cs.DS2025

Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness

Elena Gribelyuk, Honghao Lin, David P. Woodruff +2

We introduce a novel technique for ``lifting'' dimension lower bounds for linear sketches in the real-valued setting to dimension lower bounds for linear sketches with polynomially…

cs.DS2024

A Strong Separation for Adversarially Robust $ℓ_{0}$ 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…

cs.DS2023

$ℓ_{p}$ -Regression in the Arbitrary Partition Model of Communication

Yi Li, Honghao Lin, David P. Woodruff

We consider the randomized communication complexity of the distributed $ℓ_{p}$ -regression problem in the coordinator model, for $p \in (0, 2]$ . In this problem, there is a coordinat…

cs.LG2023

Learning the Positions in CountSketch

Yi Li, Honghao Lin, Simin Liu +2

We consider sketching algorithms which first compress data by multiplication with a random sketch matrix, and then apply the sketch to quickly solve an optimization problem, e.g.,…

cs.DS2022

The $ℓ_{p}$ -Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines

Yi Li, Honghao Lin, David P. Woodruff

In the $ℓ_{p}$ -subspace sketch problem, we are given an $n \times d$ matrix $A$ with $n > d$ , and asked to build a small memory data structure $Q (A, ε)$ so that, for any query vector…

cs.DS2022

Streaming Algorithms with Large Approximation Factors

Yi Li, Honghao Lin, David P. Woodruff +1

We initiate a broad study of classical problems in the streaming model with insertions and deletions in the setting where we allow the approximation factor $α$ to be much larger th…

cs.DS2022★ 3 cited

Learning Augmented Binary Search Trees

Honghao Lin, Tian Luo, David P. Woodruff

A treap is a classic randomized binary search tree data structure that is easy to implement and supports O(\log n) expected time access. However, classic treaps do not take advanta…

cs.DS2022★ 1 cited

Triangle and Four Cycle Counting with Predictions in Graph Streams

Justin Y. Chen, Talya Eden, Piotr Indyk +7

We propose data-driven one-pass streaming algorithms for estimating the number of triangles and four cycles, two fundamental problems in graph analytics that are widely studied in…

cs.LG2021

Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Time

Yu Cheng, Honghao Lin

We study the problem of learning Bayesian networks where an $ε$ -fraction of the samples are adversarially corrupted. We focus on the fully-observable case where the underlying grap…

cs.LG2021

Learning-Augmented Sketches for Hessians

Yi Li, Honghao Lin, David P. Woodruff

Sketching is a dimensionality reduction technique where one compresses a matrix by linear combinations that are chosen at random. A line of work has shown how to sketch the Hessian…

cs.LG2020★ 1 cited

Learning the Positions in CountSketch

Simin Liu, Tianrui Liu, Ali Vakilian +2

We consider sketching algorithms which first quickly compress data by multiplication with a random sketch matrix, and then apply the sketch to quickly solve an optimization problem…

A Proof of the Most Informative Boolean Function Conjecture

Nearly Optimal Strong Coresets for ℓp​ Subspace Approximation

A Near-Optimal Lower Bound for Prefix-Matrix Factorizations

Pairwise-Independent Dithering for Single-Stage Hadamard Quantization

The Condition-Number Barrier in Sparse Least Squares

Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity

Adversarial Robustness for Small Frequency Moments and a Weak Equivalence Theorem for Turnstile Streams

Adversarial Robustness on Insertion-Deletion Streams

Lp​ Sampling in Distributed Data Streams with Applications to Adversarial Robustness

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

On Sketching Trimmed Statistics

Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness

A Strong Separation for Adversarially Robust ℓ0​ Estimation for Linear Sketches

Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms

Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut

ℓp​-Regression in the Arbitrary Partition Model of Communication

Learning the Positions in CountSketch

The ℓp​-Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines

Streaming Algorithms with Large Approximation Factors

Learning Augmented Binary Search Trees

Triangle and Four Cycle Counting with Predictions in Graph Streams

Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Time

Learning-Augmented Sketches for Hessians

Learning the Positions in CountSketch

Nearly Optimal Strong Coresets for $ℓ_{p}$ Subspace Approximation

$L_{p}$ Sampling in Distributed Data Streams with Applications to Adversarial Robustness

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

A Strong Separation for Adversarially Robust $ℓ_{0}$ Estimation for Linear Sketches

$ℓ_{p}$ -Regression in the Arbitrary Partition Model of Communication

The $ℓ_{p}$ -Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines