I am now an assistant professor in the Divison of Mathematial 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:

~~1 PhD studentship starting in January 2019. See the School's website for application details.~~- 2 postdoctoral positions between Jan 2019 and Dec 2021 (flexible starting date; appointment up to 2 years, extension subject to funding). The project aims to gain a better understanding of basic matrix and linear algebraic problems in data stream setting. It concentrates on designing and analysing space- and/or time-efficient algorithms. Gross salary will be about 54000-60000 SGD/year (dependent on previous qualifications and experience) with additional performance bonus of up to 3 months. Income tax rate is low in Singapore, about ~4% for a gross income of 70000 SGD (see the IRAS website). Travel support is available.

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 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. Clustering Distributed Data with Outliers.
*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])

- 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
*l*_{∞}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. Clustering Distributed Data with Outliers.

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. An Asymptotically 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 2. Jan 2019 -- Dec 2021. Amount awarded: 453,060 SGD + 140,000 SGD for 1 scholarship.

- At Nanyang Technological University
- MH1812. Discrete Mathematics.
- Autumn 2020. (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.
- MH2401. Algorithms and Computing III.
- Autumn 2016. (co-teaching with Fedor Duzhin)
- At Shanghai Jiaotong University
- Summer 2018. Probability and Computing.

- Conference programme committee: ISAAC'18, FOCS'20
- Workshop organizer:
- March 2021. Algorithms and Foundations for Data Science at NUS-IMS. (co-organizing with David Woodruff)