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. Adviser: Prof. Martin Strauss |

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. Deterministic Sparse Fourier Transform with an
*l*_{∞}Guarantee.

Manuscript. arxiv:1903.00995

- 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])

- Yi Li, Ruosong Wang, David Woodruff. Tight Bounds for the Subspace Sketch Problem with Applications.

Proceedings of*SODA*2020, to appear. 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. arxiv:1709.02917 - 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. arXiv:1604.08679 - 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. pdf

- 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
- 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.
- MH2401. Algorithms and Computing III.
- Autumn 2016. (co-teaching with Fedor Duzhin)
- At University of Michigan
- Winter 2010. EECS477. Introduction to Algorithms. Teaching assistant for Dr Seth Pettie.
- At Shanghai Jiaotong University
- Summer 2018. Probability and Computing.