Yi Li

activity

20092026

most citedDistributed Partial Clustering

12 citations · 39 across the 25 of their papers we have counts for

collaborators

31 papers

cs.DS2026

A Near-Optimal Lower Bound for $ℓ_{p}$ -Subspace Embeddings, $1 \leq p < 2$

Yi Li

For $d \geq 2$ , $p \geq 1$ and $ε > 0$ , let $N_{p} (d, ε)$ be the smallest integer $N$ such that for every integer $n$ and every $A \in R^{n \times d}$ , there exists a matrix $Φ\i…

math.FA2026

Optimal Embeddings of Constant-Dimensional Subspaces of $L^{p}$ into $ℓ_{p}^{N}$

Yi Li

For $d \geq 2$ , $p \geq 1$ and $ε > 0$ , let $N_{p} (d, ε)$ be the smallest integer $N$ such that every $d$ -dimensional subspace of $L^{p} [0, 1]$ admits a linear embedding into $ℓ_{p}^{N}$ w…

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…

A Near-Optimal Lower Bound for ℓp​-Subspace Embeddings, 1≤p<2

Optimal Embeddings of Constant-Dimensional Subspaces of Lp into ℓpN​

ℓ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

A Near-Optimal Lower Bound for $ℓ_{p}$ -Subspace Embeddings, $1 \leq p < 2$

Optimal Embeddings of Constant-Dimensional Subspaces of $L^{p}$ into $ℓ_{p}^{N}$

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

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