## Li, Yi ()I am an assistant professor in the Divison of Mathematics of the School of Physical and Mathematical Sciences at Nanyang Technological University.
Previously, I obtained my PhD from University of Michigan in 2013, under the supervisor of Martin Strauss. Afterwards I was a postdoc at the Simons Institute for the Theory of Computing, Max-Planck Institute for Informatics and Harvard University (supervised by Jelani Nelson). |

**Research Interests**

- Algorithms for massive datasets, data stream algorithms
- Dimension reduction, numerical linear algebra
- Sparse recovery and compressive sensing

**Papers**

- Sudipto Guha, Yi Li and Qin Zhang. Clustering Distributed Data with Outliers.

Manuscript. - 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. pdf - 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.

Accepted to*ACM Transactions on Algorithms.*

(This version supercedes a preliminary version that appeared in the Proceedings of*ICALP*2014,*LNCS*8572, pp 538--550 and a preliminary full version at arxiv:1402.1726) - 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.

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

(This version supercedes a preliminary version that appeared in the Proceedings of RANDOM/APPROX 2012,*LNCS*7408, pp 61-72.)

**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):436-453, 2012. pdf

(A preliminary version appeared in the Proceedings of*STOC*2010, pp 475-484.)

**Teaching**

**Talks** (excluding conference presentations)

**Miscellaneous**