## Li, Yi ()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: leeyi@umi??.edu, where each ? represents exactly one character. |

**Education**

2010 - 2013 | Ph. D. in Computer Science and Engineering,
University of Michigan. Adviser: Prof. Martin Strauss |

2008 - 2010 | M. Sc., University of Michigan. |

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

**Papers**

- Yi Li and Vasileios Nakos. Sublinear-Time Algorithms for Compressive Phase Retrieval.
*Manuscript*. arxiv:1709.02917 - Yi Li, Vasileios Nakos and David Woodruff. On Low-Risk Heavy Hitters and Sparse Recovery Schemes.
*Manuscript*. 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.
*Manuscript*. - Yi Li and David Woodruff. Embeddings of Schatten Norms with Applications to Data Streams.

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

Proceedings of*SPAA*2017. One of two co-winners of 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. 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.

*ACM Transactions on Algorithms*, Vol. 13, No. 3, pp 32:1--32:26.

(This version supercedes a preliminary version that appeared in the 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.

*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.)

**Talks** (excluding conference presentations)

**Teaching**

- At Nanyang Technological University
- Autumn 2017. MH2500. Introduction to Probability and Statistics. (co-teaching with Chan Song Heng)
- Spring 2017. MAS723. Topics in Probability and Statistics I: High-dimensional Probability
- Autumn 2016. MH2401. Algorithms and Computing III. (co-teaching with Fedor Duzhin)
- At University of Michigan
- Winter 2010. EECS477. Introduction to Algorithms. Teaching assistant for Dr Seth Pettie.