I am now an assistant professor in the Divison of Mathematical Sciences at Nanyang Technological University.

Previously, I was a postdoc at Harvard University (supervised by Jelani Nelson), a postdoc at the Max-Planck Institute for Informatics in Saarbruecken, Germany and a research fellow at the Simons Institute for the Theory of Computing.

Email:

Low-distortion metric embeddings

Compressive sensing and signal processing

Theoretical computer science

2010 - 2013 | Ph. D. in Computer Science and Engineering,
University of Michigan. |

2008 - 2010 | M. Sc. in Computer Science and Engineering, University of Michigan. |

2004 - 2008 | B. Eng. in Computer Science (ACM Honoured Class), Shanghai Jiao Tong University. |

- Yi Li, Honghao Lin and David P. Woodruff. Learning-Augmented Sketches for Hessians.

arXiv:2102.12317

- Zhengyang Guo, Yi Li and Shaoyu Pei. Expected Size of Random Tukey Layers and Convex Layers.
*Computational Geometry: Theory and Applications*103, Article No. 101856, Apr 2022. pdf - Yi Li, Ruosong Wang, David Woodruff. Tight Bounds for the Subspace Sketch Problem with Applications.
*SIAM J. Comp.***50**(4), pp 1287--1335. pdf

(This version supersedes [C19]) - Yi Li and Vasileios Nakos. Sublinear-Time Algorithms for Compressive Phase Retrieval.
*IEEE Trans. Info. Theory*,**66**(11), pp 7302--7310, 2020. pdf

(This paper supersedes, and is radically different from, [C14]) - Yi Li, Huy Le Nguyen and David Woodruff. On Approximating Matrix Norms in a Stream.
*SIAM J. Comput.*,**48**(6), pp 1643--1697, 2019. pdf

(This version supersedes [C4], [C9] and part of [C11]) - Sudipto Guha, Yi Li and Qin Zhang. Distributed Partial Clustering.
*ACM Transactions on Parallel Computing***6**(3), pp 11:1--11:20, October 2019. (Special issue on SPAA 2017) pdf

(This version supersedes [C12]) - Anna Gilbert, Yi Li, Ely Porat and Martin Strauss.
For-all Sparse Recovery in Near-Optimal Time.

*ACM Transactions on Algorithms***13**(3), pp 32:1--32:26, August 2017. pdf

(This version supersedes [C6]) - Petros Boufounos, Volkan Cevher, Anna Gilbert, Yi Li and
Martin Strauss. What's the Frequency, Kenneth?: Sublinear
Fourier Sampling Off the Grid.

*Algorithmica***73**(2), pp 261-288, 2015. pdf

(This version supersedes [C2])

Update: A small tweak in the hashing lemma shows that diluting S^1 by*k*/*η*, instead of 1/*η*, would be enough. The sampling duration can be brought down to 1/*η*from*k*/*η*. - Anna Gilbert, Yi Li, Ely Porat and Martin Strauss.
Approximate Sparse Recovery: Optimizing Time and
Measurements.

*SIAM J. Comput.***41**(2), pp 436-453, 2012. pdf

(This version supersedes [C1])

- Yi Li, Honghao Lin, David Woodruff, Yuheng Zhang. Streaming Algorithms with Large Approximation Factors.

Proceedings of RANDOM/APPROX 2022, to appear. - Cheng Chen, Yi Li, Yiming Sun. Online Active Regression.

Proceedings of*ICML*2022, to appear. (Long presentation)

Results superceded by the updated version arXiv:2207.05945 - Yi Li, Mingmou Liu. Lower Bounds for Sparse Oblivious Subspace Embeddings.

Proceedings of*PODS*2022, pp 251--260. arXiv:2112.10987 - Yi Li, Yan Song, Qin Zhang. Learning to Cluster via Same-Cluster Queries.

Proceedings of*CIKM*2021, pp 978--987. arXiv:2108.07383 - Yi Li and David P. Woodruff. The Product of Gaussian Matrices is Close to Gaussian.

Proceedings of RANDOM/APPROX 2021,*LIPIcs*Vol. 207, pp 35:1--35:22. arXiv:2108.09887 - Yi Li, David P. Woodruff and Taisuke Yasuda. Exponentially Improved Dimensionality Reduction for
*ℓ*_{1}: Subspace Embeddings and Independence Testing.

Proceedings of Machine Learning Research 134:3111--3195, 2021. (Proceedings of*COLT*2021) arXiv:2104.12946 - Yifei Jiang, Yi Li, Yiming Sun, Jiaxin Wang, David Woodruff. Single Pass Entrywise-Transformed Low Rank Approximation.

Proceedings of Machine Learning Research 139:4982--4991, 2021. (Proceedings of*ICML*2021) arxiv:2107.07889 - Zhengyang Guo and Yi Li. Geometric Cover with Outliers Removal.

Proceedings of STACS 2021,*LIPIcs*Vol. 187, pp 39:1--39:15. pdf - Alexandr Andoni, Collin Burns, Yi Li, Sepideh Mahabadi, David Woodruff. Streaming Complexity of SVMs.

Proceedings of RANDOM/APPROX 2020,*LIPIcs*Vol. 176, pp 50:1--50:22. arxiv:2007.03633 - Yi Li, Ruosong Wang, Lin Yang, Hanrui Zhang. Nearly Linear Row Sampling Algorithm for Quantile Regression.

Proceedings of Machine Learning Research 119:1888--1898, 2020. (Proceedings of*ICML*2020). arxiv:2006.08397 - Yi Li and David Woodruff. Input-Sparsity Low Rank Approximation in Schatten Norm.

Proceedings of Machine Learning Research 119:11124--11132, 2020. (Proceedings of*ICML*2020). arxiv:2004.12646 - Yi Li and Vasileios Nakos. Deterministic Sparse Fourier Transform with an
*ℓ*_{∞}Guarantee.

Proceedings of ICALP 2020,*LIPIcs*Vol. 168, pp 77:1--77:14. arxiv:1903.00995 - Tanqiu Jiang, Yi Li, Honghao Lin, Yisong Ruan, David Woodruff. Learning-Augmented Data Stream Algorithms.

Proceedings of*ICLR*2020. (No physical publication) Open Review link - Yi Li, Ruosong Wang, David Woodruff. Tight Bounds for the Subspace Sketch Problem with Applications.

Proceedings of*SODA*2020, pp 1655--1674. arxiv:1904.05543 - Maria-Florina Balcan, Yi Li, David Woodruff, Hongyang Zhang. Testing Matrix Rank, Optimally.

Proceedings of*SODA*2019, pp 727--746. arxiv:1810.08171 - Yi Li and Vasileios Nakos. Deterministic Heavy Hitters with Sublinear Query Time.

Proceedings of RANDOM/APPROX 2018,*LIPIcs*Vol. 116, pp 18:1--18:18. arxiv:1712.01971 - Yi Li, Vasileios Nakos and David Woodruff. On Low-Risk Heavy Hitters and Sparse Recovery Schemes.

Proceedings of RANDOM/APPROX 2018,*LIPIcs*Vol. 116, pp 19:1--19:13. arxiv:1709.02919 - Vladimir Braverman, Stephen Chestnut, Robert Krauthgamer, Yi Li, David Woodruff, Lin Yang. Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order.
*Proceedings of Machine Learning Research*80:648-657, 2018. (Proceedings of*ICML*2018) arxiv:1609.05885 - Yi Li and Vasileios Nakos. Sublinear-Time Algorithms for Compressive Phase Retrieval.

Proceedings of*ISIT*2018, pp 2301--2305. - Yi Li and David Woodruff. Embeddings of Schatten Norms with Applications to Data Streams.

Proceedings of*ICALP*2017, pp 60:1--60:14. pdf - Sudipto Guha, Yi Li and Qin Zhang. Distributed Partial Clustering.

Proceedings of*SPAA*2017, pp 143--152. Co-winner of the**Best Paper award**. - Yi Li and David Woodruff. Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings.

Proceedings of RANDOM/APPROX 2016,*LIPIcs*Vol. 60, 39:1--39:11. pdf - Yuqing Ai, Wei Hu, Yi Li and David Woodruff. New Characterizations in Turnstile Streams with Applications.

Proceedings of*CCC*2016, pp 20:1--20:22. pdf - Yi Li and David Woodruff. On Approximating Functions of the Singular Values in a Stream.

Proceedings of*STOC*2016, pp 767--780. - Yi Li, Xiaoming Sun, Chengu Wang and David Woodruff.
On The Communication Complexity of Linear Algebraic Problems in the Message Passing Model.

Proceedings of*DISC*2014, pp 499--513. Full version: arxiv:1407.4755 - Yi Li, Zhengyu Wang and David Woodruff. Improved Testing of Low Rank Matrices.

Proceedings of*SIGKDD*2014, pp 691--700.**One of nine best papers.** - Anna Gilbert, Yi Li, Ely Porat and Martin Strauss.
For-all Sparse Recovery in Near-Optimal Time.

Proceedings of*ICALP*2014,*LNCS*8572, pp 538--550 - Yi Li, Huy Le Nguyen and David Woodruff. Turnstile
Streaming Algorithms Might as Well Be Linear Sketches.

Proceedings of*STOC*2014, pp 174--183. pdf - Yi Li, Huy Le Nguyen and David Woodruff. On Sketching
Matrix Norms and the Top Singular Vector.

Proceedings of*SODA*2014, pp 1562--1581. - Yi Li and David Woodruff. A Tight Lower
Bound for High Frequency Moment Estimation for Small
Error.

Proceedings of RANDOM/APPROX 2013,*LNCS*8906, pp 623--638. pdf of full version - Petros Boufounos, Volkan Cevher, Anna Gilbert, Yi Li and
Martin Strauss. What's the Frequency, Kenneth?: Sublinear
Fourier Sampling Off the Grid.

Proceedings of RANDOM/APPROX 2012,*LNCS*7408, pp 61-72. - Anna Gilbert, Yi Li, Ely Porat and Martin Strauss.
Approximate Sparse Recovery: Optimizing Time and
Measurements.

Proceedings of*STOC*2010, pp 475-484.

- MOE AcRF Tier 1. Mar 2022 -- Aug 2024. Amount awarded: 189,000 SGD.
- MOE AcRF Tier 2. Jan 2019 -- Mar 2022. Amount awarded: 453,060 SGD + 140,000 SGD for 1 scholarship.

- At Nanyang Technological University
- MH1812. Discrete Mathematics.
- Autumn 2020*, 2021*, 2022*. (* denotes co-teaching with Jian Guo)
- MH2500. Introduction to Probability and Statistics.
- Autumn 2017*, 2018*, 2019. (* denotes co-teaching with Chan Song Heng)
- MAS723. Topics in Probability and Statistics I: Probability in High-dimensional Spaces
- Spring 2017, 2018, 2019, 2020, 2021, 2022.
- MH2401. Algorithms and Computing III.
- Autumn 2016. (co-teaching with Fedor Duzhin)
- At Shanghai Jiaotong University
- Summer 2018, 2021, 2022. Probability and Computing.

- Conference programme committee: ISAAC'18, FOCS'20, RANDOM'21
- Editor of the SICOMP special issue for FOCS'20
- Workshop organizer:
- May-June 2022. Algorithms and Foundations for Data Science at NUS-IMS. (co-organizing with David Woodruff)