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

Journal Publications

  1. 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])
  2. 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])
  3. 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])
  4. 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])
  5. 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/η.
  6. 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. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. Maria-Florina Balcan, Yi Li, David Woodruff, Hongyang Zhang. Testing Matrix Rank, Optimally.
    Proceedings of SODA 2019, pp 727--746. arxiv:1810.08171
  8. 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
  9. 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
  10. 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
  11. Yi Li and Vasileios Nakos. Sublinear-Time Algorithms for Compressive Phase Retrieval.
    Proceedings of ISIT 2018, pp 2301--2305.
  12. Yi Li and David Woodruff. Embeddings of Schatten Norms with Applications to Data Streams.
    Proceedings of ICALP 2017, pp 60:1--60:14. pdf
  13. 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.
  14. 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
  15. 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
  16. Yi Li and David Woodruff. On Approximating Functions of the Singular Values in a Stream.
    Proceedings of STOC 2016, pp 767--780.
  17. 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
  18. 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.
  19. 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
  20. 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
  21. Yi Li, Huy Le Nguyen and David Woodruff. On Sketching Matrix Norms and the Top Singular Vector.
    Proceedings of SODA 2014, pp 1562--1581.
  22. 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
  23. 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.
  24. 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

    Services

    Miscellaneous