Yi Li

According to our database, Yi Li authored at least 45 papers between 2012 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms.

Yi Li, Honghao Lin, David P. Woodruff

Proceedings of the Twelfth International Conference on Learning Representations, 2024

2023

The ℓ_<i>p</i>-Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines.

Yi Li, Honghao Lin, David P. Woodruff

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Learning the Positions in CountSketch.

Yi Li, Honghao Lin, Simin Liu, Ali Vakilian, David P. Woodruff

Proceedings of the Eleventh International Conference on Learning Representations, 2023

ℓ_p-Regression in the Arbitrary Partition Model of Communication.

Yi Li, Honghao Lin, David P. Woodruff

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022

Higher Lower Bounds for Sparse Oblivious Subspace Embeddings.

Yi Li, Mingmou Liu

CoRR, 2022

The 𝓁_p-Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines.

Yi Li, Honghao Lin, David P. Woodruff

CoRR, 2022

Expected size of random Tukey layers and convex layers.

Zhengyang Guo, Yi Li, Shaoyu Pei

Comput. Geom., 2022

Lower Bounds for Sparse Oblivious Subspace Embeddings.

Yi Li, Mingmou Liu

Proceedings of the PODS '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12, 2022

Online Active Regression.

Cheng Chen, Yi Li, Yiming Sun

Proceedings of the International Conference on Machine Learning, 2022

Streaming Algorithms with Large Approximation Factors.

Yi Li, Honghao Lin, David P. Woodruff, Yuheng Zhang

Proceedings of the Approximation, 2022

2021

Tight Bounds for the Subspace Sketch Problem with Applications.

Yi Li, Ruosong Wang, David P. Woodruff

SIAM J. Comput., 2021

Exponentially Improved Dimensionality Reduction for 𝓁₁: Subspace Embeddings and Independence Testing.

Yi Li, David P. Woodruff, Taisuke Yasuda

CoRR, 2021

Learning-Augmented Sketches for Hessians.

Yi Li, Honghao Lin, David P. Woodruff

CoRR, 2021

Geometric Cover with Outliers Removal.

Zhengyang Guo, Yi Li

Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, 2021

Single Pass Entrywise-Transformed Low Rank Approximation.

Yifei Jiang, Yi Li, Yiming Sun, Jiaxin Wang, David P. Woodruff

Proceedings of the 38th International Conference on Machine Learning, 2021

Exponentially Improved Dimensionality Reduction for l1: Subspace Embeddings and Independence Testing.

Yi Li, David P. Woodruff, Taisuke Yasuda

Proceedings of the Conference on Learning Theory, 2021

Learning to Cluster via Same-Cluster Queries.

Yi Li, Yan Song, Qin Zhang

Proceedings of the CIKM '21: The 30th ACM International Conference on Information and Knowledge Management, Virtual Event, Queensland, Australia, November 1, 2021

The Product of Gaussian Matrices Is Close to Gaussian.

Yi Li, David P. Woodruff

Proceedings of the Approximation, 2021

2020

Sublinear-Time Algorithms for Compressive Phase Retrieval.

Yi Li, Vasileios Nakos

IEEE Trans. Inf. Theory, 2020

The Expected Size of Random Convex Layers and Convex Shells.

Zhengyang Guo, Yi Li, Shaoyu Pei

CoRR, 2020

Minimum Enclosing Parallelogram with Outliers.

Zhengyang Guo, Yi Li

CoRR, 2020

Input-Sparsity Low Rank Approximation in Schatten Norm.

Yi Li, David P. Woodruff

Proceedings of the 37th International Conference on Machine Learning, 2020

Learning-Augmented Data Stream Algorithms.

Tanqiu Jiang, Yi Li, Honghao Lin, Yisong Ruan, David P. Woodruff

Proceedings of the 8th International Conference on Learning Representations, 2020

Deterministic Sparse Fourier Transform with an ℓ_∞ Guarantee.

Yi Li, Vasileios Nakos

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

Streaming Complexity of SVMs.

Alexandr Andoni, Collin Burns, Yi Li, Sepideh Mahabadi, David P. Woodruff

Proceedings of the Approximation, 2020

2019

Distributed Partial Clustering.

Sudipto Guha, Yi Li, Qin Zhang

ACM Trans. Parallel Comput., 2019

On Approximating Matrix Norms in Data Streams.

Yi Li, Huy L. Nguyen, David P. Woodruff

SIAM J. Comput., 2019

Deterministic Sparse Fourier Transform with an ell_infty Guarantee.

Yi Li, Vasileios Nakos

CoRR, 2019

Testing Matrix Rank, Optimally.

Maria-Florina Balcan, Yi Li, David P. Woodruff, Hongyang Zhang

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018

Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order.

Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, Yi Li, David P. Woodruff, Lin F. Yang

Proceedings of the 35th International Conference on Machine Learning, 2018

On Low-Risk Heavy Hitters and Sparse Recovery Schemes.

Yi Li, Vasileios Nakos, David P. Woodruff

Proceedings of the Approximation, 2018

Deterministic Heavy Hitters with Sublinear Query Time.

Yi Li, Vasileios Nakos

Proceedings of the Approximation, 2018

2017

For-All Sparse Recovery in Near-Optimal Time.

Anna C. Gilbert, Yi Li, Ely Porat, Martin J. Strauss

ACM Trans. Algorithms, 2017

Embeddings of Schatten Norms with Applications to Data Streams.

Yi Li, David P. Woodruff

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

On approximating functions of the singular values in a stream.

Yi Li, David P. Woodruff

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

New Characterizations in Turnstile Streams with Applications.

Yuqing Ai, Wei Hu, Yi Li, David P. Woodruff

Proceedings of the 31st Conference on Computational Complexity, 2016

Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings.

Yi Li, David P. Woodruff

Proceedings of the Approximation, 2016

2015

What's the Frequency, Kenneth?: Sublinear Fourier Sampling Off the Grid.

Petros Boufounos, Volkan Cevher, Anna C. Gilbert, Yi Li, Martin J. Strauss

Algorithmica, 2015

2014

On the Communication Complexity of Linear Algebraic Problems in the Message Passing Model.

Yi Li, Xiaoming Sun, Chengu Wang, David P. Woodruff

Proceedings of the Distributed Computing - 28th International Symposium, 2014

Turnstile streaming algorithms might as well be linear sketches.

Yi Li, Huy L. Nguyen, David P. Woodruff

Proceedings of the Symposium on Theory of Computing, 2014

On Sketching Matrix Norms and the Top Singular Vector.

Yi Li, Huy L. Nguyen, David P. Woodruff

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Improved testing of low rank matrices.

Yi Li, Zhengyu Wang, David P. Woodruff

Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2014

2013

Sublinear Time Algorithms for the Sparse Recovery Problem.

Yi Li

PhD thesis, 2013

A Tight Lower Bound for High Frequency Moment Estimation with Small Error.

Yi Li, David P. Woodruff

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012

Approximate Sparse Recovery: Optimizing Time and Measurements.

Anna C. Gilbert, Yi Li, Ely Porat, Martin J. Strauss

SIAM J. Comput., 2012