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:

Open Positions

Interested applicants are welcome to contact me.

Research Interests

Algorithms for massive data sets, data streaming algorithms
Low-distortion metric embeddings
Compressive sensing and signal processing
Theoretical computer science

Education

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.

Manuscripts

Journal Publications

  1. 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])
  2. 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])
  3. 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])
  4. 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/η.
  5. 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])

Conference Publications

  1. Yi Li, Ruosong Wang, David Woodruff. Tight Bounds for the Subspace Sketch Problem with Applications.
    Proceedings of SODA 2020, to appear. arxiv:1904.05543
  2. Maria-Florina Balcan, Yi Li, David Woodruff, Hongyang Zhang. Testing Matrix Rank, Optimally.
    Proceedings of SODA 2019, pp 727--746. arxiv:1810.08171
  3. 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
  4. 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
  5. 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
  6. Yi Li and Vasileios Nakos. Sublinear-Time Algorithms for Compressive Phase Retrieval.
    Proceedings of ISIT 2018, pp 2301--2305. arxiv:1709.02917
  7. Yi Li and David Woodruff. Embeddings of Schatten Norms with Applications to Data Streams.
    Proceedings of ICALP 2017, pp 60:1--60:14. pdf
  8. 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.
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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.
  14. 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
  15. 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
  16. 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
  17. 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
  18. 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.
  19. Anna Gilbert, Yi Li, Ely Porat and Martin Strauss. Approximate Sparse Recovery: Optimizing Time and Measurements.
    Proceedings of STOC 2010, pp 475-484.

Grants

Talks (excluding conference presentations)

  • The lp-subspace sketch problem with applications to non-embeddability. Shanghai Jiaotong University, May 2019 and Xiamen University, June 2019.
  • Matrix-related Problems in Data Streams. Workshop on Random Matrices, Stochastic Geometry and Related Topics. Institute of Mathematical Sciences, NUS, 2019.
  • Estimating the lp and Schatten Norms in Data Stream Model. NUS Department of Statistics Seminar Talk, 2019.
  • Estimating the Schatten Norms in Streaming Model. Shanghai Jiaotong University, 2018.
  • Estimating the Schatten Norms in Streaming Model. NII Shonan Meeting "Processing Big Data Streams", 2017.
  • Improved Sparse Recovery Algorithms. Dagstuhl Seminar 17181 "Theory and Applications of Hashing", 2017.
  • Sublinear-time Algorithms for the Sparse Recovery Problem. Workshop on Sparse Representations & Compressive Sensing, 2017.
  • Estimating the Schatten Norms in Streaming Model. DIMACS Workshop on E+M=C2, 2017.
  • Introduction to the Data Stream Algorithms. Xiamen University, 2016
  • Introduction to the Sparse Recovery Problem. Fuzhou University, 2016
  • Introduction to the Data Stream Algorithms. Math Colloquium, Nanyang Technological University, 2016.
  • Data Streaming Algorithms. MAS Seminar, Nanyang Technological University, 2015.
  • For-all Sparse Recovery in Near-Optimal Time. Theory of Computation Seminar, Harvard University, 2015.
  • A Brief Introduction to the Sublinear-time Sparse Recovery Problem. MPI for Informatics, 2014.
  • Sublinear Fourier Sampling Off the Grid. Workshop on Sparse Fourier Transform, MIT, 2013.
  • Approximate Sparse Recovery: Optimizing Time and Measurements. Minisymposium on Combinatorics and Data Science, Shanghai Jiaotong University, 2011.
  • Approximate Sparse Recovery: Optimizing Time and Measurements. DIMACS Workshop on Network Data Streaming and Compressive Sensing, 2010.
  • Teaching

    Functional Analysis Exercises