Awarded Papers

• [ bib ] Path Finding Methods for Linear Programming: Solving Linear Programs in $\tilde{O}(\sqrt{\mathrm{rank}})$ Iterations and Faster Algorithms for Maximum Flow
  with Aaron Sidford on FOCS 2014
  

  First theoretic improvement on the running time of linear programming since 1986.
  Best paper and best student paper in FOCS 2014.
  Selected as a notable article in computing in 2014 by Computing Reviews.

  @inproceedings{DBLP:conf/focs/LeeS14,
    author    = {Yin Tat Lee and
                 Aaron Sidford},
    title     = {Path Finding Methods for Linear Programming: Solving Linear Programs
                 in {\~{O}}(sqrt(rank)) Iterations and Faster Algorithms for Maximum Flow},
    booktitle = {55th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
                 2014, Philadelphia, PA, USA, October 18-21, 2014},
    pages     = {424--433},
    year      = {2014},
    url       = {https://doi.org/10.1109/FOCS.2014.52},
    doi       = {10.1109/FOCS.2014.52}
  }
  

• [ bib ] An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
  with Jonathan Kelner, Lorenzo Orecchia, and Aaron Sidford on SODA 2014
  

  First almost-linear-time method for undirected maxflow.
  Best paper in SODA 2014. Improved.

  @inproceedings{DBLP:conf/soda/KelnerLOS14,
    author    = {Jonathan A. Kelner and
                 Yin Tat Lee and
                 Lorenzo Orecchia and
                 Aaron Sidford},
    title     = {An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected
                 Graphs, and its Multicommodity Generalizations},
    booktitle = {Proceedings of the Twenty-Fifth Annual {ACM-SIAM} Symposium on Discrete
                 Algorithms, {SODA} 2014, Portland, Oregon, USA, January 5-7, 2014},
    pages     = {217--226},
    year      = {2014},
    url       = {https://doi.org/10.1137/1.9781611973402.16},
    doi       = {10.1137/1.9781611973402.16}
  }
  

• [ bib ] A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization
  with Aaron Sidford and Sam Chiu-wai Wong on FOCS 2015
  

  First nearly-cubic-time method for convex problems with first-order information.
  Best student paper in FOCS 2015.

  @inproceedings{DBLP:conf/focs/LeeSW15,
    author    = {Yin Tat Lee and
                 Aaron Sidford and
                 Sam Chiu{-}wai Wong},
    title     = {A Faster Cutting Plane Method and its Implications for Combinatorial
                 and Convex Optimization},
    booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS}
                 2015, Berkeley, CA, USA, 17-20 October, 2015},
    pages     = {1049--1065},
    year      = {2015},
    url       = {https://doi.org/10.1109/FOCS.2015.68},
    doi       = {10.1109/FOCS.2015.68}
  }
  

• [ bib ] Optimal Algorithms for Non-Smooth Distributed Optimization in Networks
  with Kevin Scaman, Francis Bach, Sebastien Bubeck, and Laurent Massoulie on NeurIPS 2018
  

  Best paper in NeurIPS 2018.

  @inproceedings{DBLP:conf/nips/ScamanBBML18,
    author    = {Kevin Scaman and
                 Francis Bach and
                 S{\'{e}}bastien Bubeck and
                 Laurent Massouli{\'{e}} and
                 Yin Tat Lee},
    title     = {Optimal Algorithms for Non-Smooth Distributed Optimization in Networks},
    booktitle = {Advances in Neural Information Processing Systems 31: Annual Conference
                 on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December
                 2018, Montr{\'{e}}al, Canada.},
    pages     = {2745--2754},
    year      = {2018},
    url       = {http://papers.nips.cc/paper/7539-optimal-algorithms-for-non-smooth-distributed-optimization-in-networks}
  }
  

Surveys

• [ bib ] The Kannan-Lovász-Simonovits Conjecture
  with Santosh Vempala on arXiv
  

  @article{DBLP:journals/corr/LeeV18,
    author    = {Yin Tat Lee and
                 Santosh S. Vempala},
    title     = {The Kannan-Lov{\'{a}}sz-Simonovits Conjecture},
    journal   = {CoRR},
    volume    = {abs/1807.03465},
    year      = {2018},
    url       = {http://arxiv.org/abs/1807.03465},
    archivePrefix = {arXiv},
    eprint    = {1807.03465}
  }
  

• [ bib ] Faster Algorithms for Convex and Combinatorial Optimization
  

  PhD thesis. Advised by Professor Jonathan A. Kelner.
  Sprowls award from MIT and A. W. Tucker Prize.

  @phdthesis{YinTatThesis,
    author    = {Yin Tat Lee},
    title     = {Faster Algorithms for Convex and Combinatorial Optimization},
    year      = {2016},
    school    = {Massachusetts Institute of Technology}
  }
  

Selected Publications

• [ bib ] A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Path
  with Sally Dong and Guanghao Ye on STOC 2021
  

  First nearly linear time algorithm for linear programs with small treewidth

  @inproceedings{DBLP:conf/stoc/DongLY21,
    author    = {Sally Dong and
                 Yin Tat Lee and
                 Guanghao Ye},
    editor    = {Samir Khuller and
                 Virginia Vassilevska Williams},
    title     = {A nearly-linear time algorithm for linear programs with small treewidth:
                 a multiscale representation of robust central path},
    booktitle = {{STOC} '21: 53rd Annual {ACM} {SIGACT} Symposium on Theory of Computing,
                 Virtual Event, Italy, June 21-25, 2021},
    pages     = {1784--1797},
    publisher = {{ACM}},
    year      = {2021},
    url       = {https://doi.org/10.1145/3406325.3451056}
  }
  

• [ bib ] Solving Linear Programs in the Current Matrix Multiplication Time
  with Michael Cohen and Zhao Song on STOC 2019
  

  First time we can solve linear programs as fast as linear systems

  @inproceedings{DBLP:conf/stoc/CohenLS19,
    author    = {Michael B. Cohen and
                 Yin Tat Lee and
                 Zhao Song},
    title     = {Solving linear programs in the current matrix multiplication time},
    booktitle = {Proceedings of the 51st Annual {ACM} {SIGACT} Symposium on Theory
                 of Computing, {STOC} 2019, Phoenix, AZ, USA, June 23-26, 2019.},
    pages     = {938--942},
    year      = {2019},
    url       = {https://doi.org/10.1145/3313276.3316303},
    doi       = {10.1145/3313276.3316303}
  }
  

• [ bib ] k-server via multiscale entropic regularization
  with Sebastien Bubeck, Michael Cohen, James Lee, and Aleksander Madry on STOC 2018
  

  First $o(k)$-competitive algorithm for k server on HST. Improved

  @inproceedings{DBLP:conf/stoc/BubeckCLLM18,
    author    = {S{\'{e}}bastien Bubeck and
                 Michael B. Cohen and
                 Yin Tat Lee and
                 James R. Lee and
                 Aleksander Madry},
    title     = {k-server via multiscale entropic regularization},
    booktitle = {Proceedings of the 50th Annual {ACM} {SIGACT} Symposium on Theory
                 of Computing, {STOC} 2018, Los Angeles, CA, USA, June 25-29, 2018},
    pages     = {3--16},
    year      = {2018},
    url       = {http://doi.acm.org/10.1145/3188745.3188798},
    doi       = {10.1145/3188745.3188798}
  }
  

• [ bib ] Convergence rate of Riemannian Hamiltonian Monte Carlo and faster polytope volume computation
  with Santosh S. Vempala on STOC 2018
  

  First(?) efficient method for sampling in polytopes.

  @inproceedings{DBLP:conf/stoc/LeeV18,
    author    = {Yin Tat Lee and
                 Santosh S. Vempala},
    title     = {Convergence rate of Riemannian Hamiltonian Monte Carlo and faster
                 polytope volume computation},
    booktitle = {Proceedings of the 50th Annual {ACM} {SIGACT} Symposium on Theory
                 of Computing, {STOC} 2018, Los Angeles, CA, USA, June 25-29, 2018},
    pages     = {1115--1121},
    year      = {2018},
    url       = {http://doi.acm.org/10.1145/3188745.3188774},
    doi       = {10.1145/3188745.3188774}
  }
  

• [ bib ] Eldan's Stochastic Localization and the {KLS} Hyperplane Conjecture: An Improved Lower Bound for Expansion
  with Santosh Vempala on FOCS 2017
  

  Any 1-Lipschitz function concentrates to its mean on isotropic logconcave distribution with $n^{1/4}$ error. Improved

  @inproceedings{DBLP:conf/focs/LeeV17,
    author    = {Yin Tat Lee and
                 Santosh S. Vempala},
    title     = {Eldan's Stochastic Localization and the {KLS} Hyperplane Conjecture:
                 An Improved Lower Bound for Expansion},
    booktitle = {58th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
                 2017, Berkeley, CA, USA, October 15-17, 2017},
    pages     = {998--1007},
    year      = {2017},
    url       = {https://doi.org/10.1109/FOCS.2017.96},
    doi       = {10.1109/FOCS.2017.96}
  }
  

• [ bib ] Kernel-based methods for bandit convex optimization
  with Sebastien Bubeck and Ronen Eldan on STOC 2017
  

  First polynomial-time method with $\mathrm{poly}(n) \sqrt{T}$-regret for bandit convex optimization.

  @inproceedings{DBLP:conf/stoc/BubeckLE17,
    author    = {S{\'{e}}bastien Bubeck and
                 Yin Tat Lee and
                 Ronen Eldan},
    title     = {Kernel-based methods for bandit convex optimization},
    booktitle = {Proceedings of the 49th Annual {ACM} {SIGACT} Symposium on Theory
                 of Computing, {STOC} 2017, Montreal, QC, Canada, June 19-23, 2017},
    pages     = {72--85},
    year      = {2017},
    url       = {http://doi.acm.org/10.1145/3055399.3055403},
    doi       = {10.1145/3055399.3055403}
  }
  

Other Publications

2022

• [ bib ] Sampling with Riemannian Hamiltonian Monte Carlo in a Constrained Space
  with Yunbum Kook, Ruoqi Shen and Santosh Vempala on NeurIPS 2022
  

  @inproceedings{DBLP:conf/nips/KookLSV22,
    author       = {Yunbum Kook and
                    Yin Tat Lee and
                    Ruoqi Shen and
                    Santosh S. Vempala},
    title        = {Sampling with Riemannian Hamiltonian Monte Carlo in a Constrained
                    Space},
    booktitle    = {NeurIPS},
    year         = {2022},
    url          = {http://papers.nips.cc/paper\_files/paper/2022/hash/cdaa7f07b0c5a7803927d20aa717132e-Abstract-Conference.html},
    timestamp    = {Thu, 11 May 2023 17:08:22 +0200},
    biburl       = {https://dblp.org/rec/conf/nips/KookLSV22.bib},
    bibsource    = {dblp computer science bibliography, https://dblp.org}
  }
  

• [ bib ] Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexity
  with Sally Dong, Haotian Jiang, Swati Padmanabhan and Guanghao Ye on NeurIPS 2022
  

  @inproceedings{DBLP:conf/nips/DongJLPY22,
    author       = {Sally Dong and
                    Haotian Jiang and
                    Yin Tat Lee and
                    Swati Padmanabhan and
                    Guanghao Ye},
    title        = {Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient
                    Oracle Complexity},
    booktitle    = {NeurIPS},
    year         = {2022},
    url          = {http://papers.nips.cc/paper\_files/paper/2022/hash/c6a79e139ec4f371701ea8cc9e06018e-Abstract-Conference.html},
    timestamp    = {Thu, 11 May 2023 17:08:22 +0200},
    biburl       = {https://dblp.org/rec/conf/nips/DongJLPY22.bib},
    bibsource    = {dblp computer science bibliography, https://dblp.org}
  }
  

• [ bib ] A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensions
  with Damek Davis, Dmitriy Drusvyatskiy, Swati Padmanabhan and Guanghao Ye on NeurIPS 2022
  

  @inproceedings{DBLP:conf/nips/DavisDLPY22,
    author       = {Damek Davis and
                    Dmitriy Drusvyatskiy and
                    Yin Tat Lee and
                    Swati Padmanabhan and
                    Guanghao Ye},
    title        = {A gradient sampling method with complexity guarantees for Lipschitz
                    functions in high and low dimensions},
    booktitle    = {NeurIPS},
    year         = {2022},
    url          = {http://papers.nips.cc/paper\_files/paper/2022/hash/2c8d9636f74d0207ff4f65956010f450-Abstract-Conference.html},
    timestamp    = {Thu, 11 May 2023 17:08:21 +0200},
    biburl       = {https://dblp.org/rec/conf/nips/DavisDLPY22.bib},
    bibsource    = {dblp computer science bibliography, https://dblp.org}
  }
  

• [ bib ] Differentially Private Fine-tuning of Language Models
  with Da Yu, Saurabh Naik, Arturs Backurs, Sivakanth Gopi, etc on NeurIPS 2022
  

  @inproceedings{DBLP:conf/iclr/YuNBGI0KLMWYZ22,
    author       = {Da Yu and
                    Saurabh Naik and
                    Arturs Backurs and
                    Sivakanth Gopi and
                    Huseyin A. Inan and
                    Gautam Kamath and
                    Janardhan Kulkarni and
                    Yin Tat Lee and
                    Andre Manoel and
                    Lukas Wutschitz and
                    Sergey Yekhanin and
                    Huishuai Zhang},
    title        = {Differentially Private Fine-tuning of Language Models},
    booktitle    = {The Tenth International Conference on Learning Representations, {ICLR}
                    2022, Virtual Event, April 25-29, 2022},
    publisher    = {OpenReview.net},
    year         = {2022},
    url          = {https://openreview.net/forum?id=Q42f0dfjECO},
    timestamp    = {Sat, 20 Aug 2022 01:15:42 +0200},
    biburl       = {https://dblp.org/rec/conf/iclr/YuNBGI0KLMWYZ22.bib},
    bibsource    = {dblp computer science bibliography, https://dblp.org}
  }
  

• [ bib ] Private Convex Optimization via Exponential Mechanism
  with Sivakanth Gopi and Daogao Liu on COLT 2022
  

  @inproceedings{DBLP:conf/colt/GopiLL22,
    author    = {Sivakanth Gopi and
                 Yin Tat Lee and
                 Daogao Liu},
    editor    = {Po{-}Ling Loh and
                 Maxim Raginsky},
    title     = {Private Convex Optimization via Exponential Mechanism},
    booktitle = {Conference on Learning Theory, 2-5 July 2022, London, {UK}},
    series    = {Proceedings of Machine Learning Research},
    volume    = {178},
    pages     = {1948--1989},
    publisher = {{PMLR}},
    year      = {2022},
    url       = {https://proceedings.mlr.press/v178/gopi22a.html}
  }
  

• [ bib ] Faster maxflow via improved dynamic spectral vertex sparsifiers
  with Jan van den Brand, Yu Gao, Arun Jambulapati, Yang P. Liu, Richard Peng and Aaron Sidford on STOC 2022
  

  @inproceedings{DBLP:conf/stoc/BrandGJLLPS22,
    author    = {Jan van den Brand and
                 Yu Gao and
                 Arun Jambulapati and
                 Yin Tat Lee and
                 Yang P. Liu and
                 Richard Peng and
                 Aaron Sidford},
    editor    = {Stefano Leonardi and
                 Anupam Gupta},
    title     = {Faster maxflow via improved dynamic spectral vertex sparsifiers},
    booktitle = {{STOC} '22: 54th Annual {ACM} {SIGACT} Symposium on Theory of Computing,
                 Rome, Italy, June 20 - 24, 2022},
    pages     = {543--556},
    publisher = {{ACM}},
    year      = {2022},
    url       = {https://doi.org/10.1145/3519935.3520068},
    doi       = {10.1145/3519935.3520068}
  }
  

• [ bib ] Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time
  with Sally Dong, Yu Gao, Gramoz Goranci, Richard Peng, Sushant Sachdeva and Guanghao Ye on SODA 2022
  

  @inproceedings{DBLP:conf/soda/DongGGLPSY22,
    author    = {Sally Dong and
                 Yu Gao and
                 Gramoz Goranci and
                 Yin Tat Lee and
                 Richard Peng and
                 Sushant Sachdeva and
                 Guanghao Ye},
    editor    = {Joseph (Seffi) Naor and
                 Niv Buchbinder},
    title     = {Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear
                 Time},
    booktitle = {Proceedings of the 2022 {ACM-SIAM} Symposium on Discrete Algorithms,
                 {SODA} 2022, Virtual Conference / Alexandria, VA, USA, January 9 -
                 12, 2022},
    pages     = {124--153},
    publisher = {{SIAM}},
    year      = {2022},
    url       = {https://doi.org/10.1137/1.9781611977073.7},
    doi       = {10.1137/1.9781611977073.7},
    timestamp = {Tue, 12 Apr 2022 11:24:56 +0200},
    biburl    = {https://dblp.org/rec/conf/soda/DongGGLPSY22.bib},
    bibsource = {dblp computer science bibliography, https://dblp.org}
  }
  

• [ bib ] Computing Lewis Weights to High Precision
  with Maryam Fazel, Swati Padmanabhan and Aaron Sidford on SODA 2022
  

  @inproceedings{DBLP:conf/soda/FazelLPS22,
    author    = {Maryam Fazel and
                 Yin Tat Lee and
                 Swati Padmanabhan and
                 Aaron Sidford},
    editor    = {Joseph (Seffi) Naor and
                 Niv Buchbinder},
    title     = {Computing Lewis Weights to High Precision},
    booktitle = {Proceedings of the 2022 {ACM-SIAM} Symposium on Discrete Algorithms,
                 {SODA} 2022, Virtual Conference / Alexandria, VA, USA, January 9 -
                 12, 2022},
    pages     = {2723--2742},
    publisher = {{SIAM}},
    year      = {2022},
    url       = {https://doi.org/10.1137/1.9781611977073.107},
    doi       = {10.1137/1.9781611977073.107},
    timestamp = {Tue, 12 Apr 2022 11:24:56 +0200},
    biburl    = {https://dblp.org/rec/conf/soda/FazelLPS22.bib},
    bibsource = {dblp computer science bibliography, https://dblp.org}
  }
  

• [ bib ] Differentially Private Fine-tuning of Language Models
  with Da Yu, Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin A Inan, Gautam Kamath, Janardhan Kulkarni, Andre Manoel, Lukas Wutschitz, Sergey Yekhanin and Huishuai Zhang on ICLR 2022
  

  @inproceedings{DBLP:conf/iclr/YuNBGI0KLMWYZ22,
    author    = {Da Yu and
                 Saurabh Naik and
                 Arturs Backurs and
                 Sivakanth Gopi and
                 Huseyin A. Inan and
                 Gautam Kamath and
                 Janardhan Kulkarni and
                 Yin Tat Lee and
                 Andre Manoel and
                 Lukas Wutschitz and
                 Sergey Yekhanin and
                 Huishuai Zhang},
    title     = {Differentially Private Fine-tuning of Language Models},
    booktitle = {The Tenth International Conference on Learning Representations, {ICLR}
                 2022, Virtual Event, April 25-29, 2022},
    publisher = {OpenReview.net},
    year      = {2022},
    url       = {https://openreview.net/forum?id=Q42f0dfjECO}
  }
  

2021

• [ bib ] Numerical Composition of Differential Privacy
  with Sivakanth Gopi and Lukas Wutschitz on NeurIPS 2021
  

  @inproceedings{DBLP:conf/nips/GopiLW21,
    author    = {Sivakanth Gopi and
                 Yin Tat Lee and
                 Lukas Wutschitz},
    editor    = {Marc'Aurelio Ranzato and
                 Alina Beygelzimer and
                 Yann N. Dauphin and
                 Percy Liang and
                 Jennifer Wortman Vaughan},
    title     = {Numerical Composition of Differential Privacy},
    booktitle = {Advances in Neural Information Processing Systems 34: Annual Conference
                 on Neural Information Processing Systems 2021, NeurIPS 2021, December
                 6-14, 2021, virtual},
    pages     = {11631--11642},
    year      = {2021},
    url       = {https://proceedings.neurips.cc/paper/2021/hash/6097d8f3714205740f30debe1166744e-Abstract.html}
  }
  

• [ bib ] Private Non-smooth ERM and SCO in Subquadratic Steps
  with Janardhan Kulkarni and Daogao Liu on NeurIPS 2021
  

  @inproceedings{DBLP:conf/nips/KulkarniLL21,
    author    = {Janardhan Kulkarni and
                 Yin Tat Lee and
                 Daogao Liu},
    editor    = {Marc'Aurelio Ranzato and
                 Alina Beygelzimer and
                 Yann N. Dauphin and
                 Percy Liang and
                 Jennifer Wortman Vaughan},
    title     = {Private Non-smooth {ERM} and {SCO} in Subquadratic Steps},
    booktitle = {Advances in Neural Information Processing Systems 34: Annual Conference
                 on Neural Information Processing Systems 2021, NeurIPS 2021, December
                 6-14, 2021, virtual},
    pages     = {4053--4064},
    year      = {2021},
    url       = {https://proceedings.neurips.cc/paper/2021/hash/211c1e0b83b9c69fa9c4bdede203c1e3-Abstract.html}
  }
  

• [ bib ] Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions
  with Ruoqi Shen and Kevin Tian on NeurIPS 2021
  

  @inproceedings{DBLP:conf/nips/LeeST21,
    author    = {Yin Tat Lee and
                 Ruoqi Shen and
                 Kevin Tian},
    editor    = {Marc'Aurelio Ranzato and
                 Alina Beygelzimer and
                 Yann N. Dauphin and
                 Percy Liang and
                 Jennifer Wortman Vaughan},
    title     = {Lower Bounds on Metropolized Sampling Methods for Well-Conditioned
                 Distributions},
    booktitle = {Advances in Neural Information Processing Systems 34: Annual Conference
                 on Neural Information Processing Systems 2021, NeurIPS 2021, December
                 6-14, 2021, virtual},
    pages     = {18812--18824},
    year      = {2021},
    url       = {https://proceedings.neurips.cc/paper/2021/hash/9c4e6233c6d5ff637e7984152a3531d5-Abstract.html}
  }
  

• [ bib ] Fast and Memory Efficient Differentially Private-SGD via JL Projections
  with Zhiqi Bu, Sivakanth Gopi, Janardhan Kulkarni, Hanwen Shen, Uthaipon Tantipongpipat on NeurIPS 2021
  

  @inproceedings{DBLP:conf/nips/BuGKLST21,
    author    = {Zhiqi Bu and
                 Sivakanth Gopi and
                 Janardhan Kulkarni and
                 Yin Tat Lee and
                 Judy Hanwen Shen and
                 Uthaipon Tantipongpipat},
    editor    = {Marc'Aurelio Ranzato and
                 Alina Beygelzimer and
                 Yann N. Dauphin and
                 Percy Liang and
                 Jennifer Wortman Vaughan},
    title     = {Fast and Memory Efficient Differentially Private-SGD via {JL} Projections},
    booktitle = {Advances in Neural Information Processing Systems 34: Annual Conference
                 on Neural Information Processing Systems 2021, NeurIPS 2021, December
                 6-14, 2021, virtual},
    pages     = {19680--19691},
    year      = {2021},
    url       = {https://proceedings.neurips.cc/paper/2021/hash/a3842ed7b3d0fe3ac263bcabd2999790-Abstract.html}
  }
  

• [ bib ] Reducing Isotropy and Volume to KLS: An $O(n^3 \psi^2)$ Volume Algorithm
  with He Jia, Aditi Laddha, and Santosh Vempala on STOC 2021
  

  @inproceedings{DBLP:conf/stoc/JiaLLV21,
    author    = {He Jia and
                 Aditi Laddha and
                 Yin Tat Lee and
                 Santosh S. Vempala},
    editor    = {Samir Khuller and
                 Virginia Vassilevska Williams},
    title     = {Reducing isotropy and volume to {KLS:} an $O(n^3 \psi^2)$
                 volume algorithm},
    booktitle = {{STOC} '21: 53rd Annual {ACM} {SIGACT} Symposium on Theory of Computing,
                 Virtual Event, Italy, June 21-25, 2021},
    pages     = {961--974},
    publisher = {{ACM}},
    year      = {2021},
    url       = {https://doi.org/10.1145/3406325.3451018}
  }
  

• [ bib ] Minimum Cost Flows, MDPs, and l1-Regression in Nearly Linear Time for Dense Instances
  with Jan van den Brand, Yang Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang on STOC 2021
  

  @inproceedings{DBLP:conf/stoc/BrandLLSS0W21,
    author    = {Jan van den Brand and
                 Yin Tat Lee and
                 Yang P. Liu and
                 Thatchaphol Saranurak and
                 Aaron Sidford and
                 Zhao Song and
                 Di Wang},
    editor    = {Samir Khuller and
                 Virginia Vassilevska Williams},
    title     = {Minimum cost flows, MDPs, and l1-regression
                 in nearly linear time for dense instances},
    booktitle = {{STOC} '21: 53rd Annual {ACM} {SIGACT} Symposium on Theory of Computing,
                 Virtual Event, Italy, June 21-25, 2021},
    pages     = {859--869},
    publisher = {{ACM}},
    year      = {2021},
    url       = {https://doi.org/10.1145/3406325.3451108}
  }
  

2020

• [ bib ] Leverage Score Sampling for Faster Accelerated Regression and ERM
  with Naman Agarwal, Sham Kakade, Rahul Kidambi and, Praneeth Netrapalli, and Aaron Sidford on ALT 2020
  

  @inproceedings{DBLP:conf/alt/AgarwalKKLNS20,
    author    = {Naman Agarwal and
                 Sham M. Kakade and
                 Rahul Kidambi and
                 Yin Tat Lee and
                 Praneeth Netrapalli and
                 Aaron Sidford},
    title     = {Leverage Score Sampling for Faster Accelerated Regression and {ERM}},
    booktitle = {Algorithmic Learning Theory, {ALT} 2020, 8-11 February 2020, San Diego,
                 CA, {USA}},
    series    = {Proceedings of Machine Learning Research},
    volume    = {117},
    pages     = {22--47},
    publisher = {{PMLR}},
    year      = {2020},
    url       = {http://proceedings.mlr.press/v117/agarwal20a.html}
  }
  

• [ bib ] Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo
  with Ruoqi Shen and Kevin Tian on COLT 2020
  

  @inproceedings{DBLP:conf/colt/LeeST20,
    author    = {Yin Tat Lee and
                 Ruoqi Shen and
                 Kevin Tian},
    title     = {Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized
                 Hamiltonian Monte Carlo},
    booktitle = {Conference on Learning Theory, {COLT} 2020, 9-12 July 2020, Virtual
                 Event [Graz, Austria]},
    series    = {Proceedings of Machine Learning Research},
    volume    = {125},
    pages     = {2565--2597},
    publisher = {{PMLR}},
    year      = {2020},
    url       = {http://proceedings.mlr.press/v125/lee20b.html}
  }
  

• [ bib ] An $O(m/\epsilon^{3.5})$-Cost Algorithm for Semidefinite Programs with Diagonal Constraints
  with Swati Padmanabhan on COLT 2020
  

  @inproceedings{DBLP:conf/colt/LeeP20,
    author    = {Yin Tat Lee and
                 Swati Padmanabhan},
    title     = {An $O(m/\epsilon^{3.5})$-Cost
                 Algorithm for Semidefinite Programs with Diagonal Constraints},
    booktitle = {Conference on Learning Theory, {COLT} 2020, 9-12 July 2020, Virtual
                 Event [Graz, Austria]},
    series    = {Proceedings of Machine Learning Research},
    volume    = {125},
    pages     = {3069--3119},
    publisher = {{PMLR}},
    year      = {2020},
    url       = {http://proceedings.mlr.press/v125/lee20c.html}
  }
  

• [ bib ] A Faster Interior Point Method for Semidefinite Programming
  with Haotian Jiang, Tarun Kathuria, Swati Padmanabhan and Zhao Song on FOCS 2020
  

  @inproceedings{DBLP:conf/focs/JiangKLP020,
    author    = {Haotian Jiang and
                 Tarun Kathuria and
                 Yin Tat Lee and
                 Swati Padmanabhan and
                 Zhao Song},
    title     = {A Faster Interior Point Method for Semidefinite Programming},
    booktitle = {61st {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
                 2020, Durham, NC, USA, November 16-19, 2020},
    pages     = {910--918},
    publisher = {{IEEE}},
    year      = {2020},
    url       = {https://doi.org/10.1109/FOCS46700.2020.00089},
    doi       = {10.1109/FOCS46700.2020.00089}
  }
  

• [ bib ] Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs
  with Jan van den Brand, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang on FOCS 2020
  

  @inproceedings{DBLP:conf/focs/BrandLNPSS0W20,
    author    = {Jan van den Brand and
                 Yin Tat Lee and
                 Danupon Nanongkai and
                 Richard Peng and
                 Thatchaphol Saranurak and
                 Aaron Sidford and
                 Zhao Song and
                 Di Wang},
    title     = {Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs},
    booktitle = {61st {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
                 2020, Durham, NC, USA, November 16-19, 2020},
    pages     = {919--930},
    publisher = {{IEEE}},
    year      = {2020},
    url       = {https://doi.org/10.1109/FOCS46700.2020.00090},
    doi       = {10.1109/FOCS46700.2020.00090}
  }
  

• [ bib ] Network size and size of the weights in memorization with two-layers neural networks
  with Sebastien Bubeck, Ronen Eldan, and Dan Mikulincer on NeurIPS 2020
  

  @inproceedings{DBLP:conf/nips/BubeckELM20,
    author    = {S{\'{e}}bastien Bubeck and
                 Ronen Eldan and
                 Yin Tat Lee and
                 Dan Mikulincer},
    title     = {Network size and size of the weights in memorization with two-layers
                 neural networks},
    booktitle = {Advances in Neural Information Processing Systems 33: Annual Conference
                 on Neural Information Processing Systems 2020, NeurIPS 2020, December
                 6-12, 2020, virtual},
    year      = {2020},
    url       = {https://proceedings.neurips.cc/paper/2020/hash/34609bdc08a07ace4e1526bbb1777673-Abstract.html}
  }
  

• [ bib ] Acceleration with a Ball Optimization Oracle
  with Yair Carmon, Arun Jambulapati, Qijia Jiang, Yujia Jin, Aaron Sidford, and Kevin Tian on NeurIPS 2020
  

  @inproceedings{DBLP:conf/nips/CarmonJJJLST20,
    author    = {Yair Carmon and
                 Arun Jambulapati and
                 Qijia Jiang and
                 Yujia Jin and
                 Yin Tat Lee and
                 Aaron Sidford and
                 Kevin Tian},
    title     = {Acceleration with a Ball Optimization Oracle},
    booktitle = {Advances in Neural Information Processing Systems 33: Annual Conference
                 on Neural Information Processing Systems 2020, NeurIPS 2020, December
                 6-12, 2020, virtual},
    year      = {2020},
    url       = {https://proceedings.neurips.cc/paper/2020/hash/dba4c1a117472f6aca95211285d0587e-Abstract.html}
  }
  

• [ bib ] Solving Tall Dense Linear Programs in Nearly Linear Time
  with Jan van den Brand, Aaron Sidford, and Zhao Song on STOC 2020
  

  First nearly linear time algorithm for linear programs with lots of constraints

  @inproceedings{DBLP:conf/stoc/BrandLSS20,
    author    = {Jan van den Brand and
                 Yin Tat Lee and
                 Aaron Sidford and
                 Zhao Song},
    title     = {Solving tall dense linear programs in nearly linear time},
    booktitle = {Proccedings of the 52nd Annual {ACM} {SIGACT} Symposium on Theory
                 of Computing, {STOC} 2020, Chicago, IL, USA, June 22-26, 2020},
    pages     = {775--788},
    publisher = {{ACM}},
    year      = {2020},
    url       = {https://doi.org/10.1145/3357713.3384309},
    doi       = {10.1145/3357713.3384309}
  }
  

• [ bib ] An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications
  with Haotian Jiang, Zhao Song, and Sam Chiu-wai Wong on STOC 2020
  

  The first cubic time algorithm for convex optimization

  @inproceedings{DBLP:conf/stoc/JiangLSW20,
    author    = {Haotian Jiang and
                 Yin Tat Lee and
                 Zhao Song and
                 Sam Chiu{-}wai Wong},
    title     = {An improved cutting plane method for convex optimization, convex-concave
                 games, and its applications},
    booktitle = {Proccedings of the 52nd Annual {ACM} {SIGACT} Symposium on Theory
                 of Computing, {STOC} 2020, Chicago, IL, USA, June 22-26, 2020},
    pages     = {944--953},
    publisher = {{ACM}},
    year      = {2020},
    url       = {https://doi.org/10.1145/3357713.3384284},
    doi       = {10.1145/3357713.3384284}
  }
  

• [ bib ] Strong Self-Concordance and Sampling
  with Aditi Laddha and Santosh Vempala on STOC 2020
  

  @inproceedings{DBLP:conf/stoc/LaddhaLV20,
    author    = {Aditi Laddha and
                 Yin Tat Lee and
                 Santosh S. Vempala},
    title     = {Strong self-concordance and sampling},
    booktitle = {Proccedings of the 52nd Annual {ACM} {SIGACT} Symposium on Theory
                 of Computing, {STOC} 2020, Chicago, IL, USA, June 22-26, 2020},
    pages     = {1212--1222},
    publisher = {{ACM}},
    year      = {2020},
    url       = {https://doi.org/10.1145/3357713.3384272},
    doi       = {10.1145/3357713.3384272}
  }
  

• [ bib ] Computing Circle Packing Representations of Planar Graphs
  with Sally Dong and Kent Quanrud on SODA 2020
  

  Nearly linear time algorithm for circle packing

  @inproceedings{DBLP:conf/soda/DongLQ20,
    author    = {Sally Dong and
                 Yin Tat Lee and
                 Kent Quanrud},
    title     = {Computing Circle Packing Representations of Planar Graphs},
    booktitle = {Proceedings of the 2020 {ACM-SIAM} Symposium on Discrete Algorithms,
                 {SODA} 2020, Salt Lake City, UT, USA, January 5-8, 2020},
    pages     = {2860--2875},
    publisher = {{SIAM}},
    year      = {2020},
    url       = {https://doi.org/10.1137/1.9781611975994.174},
    doi       = {10.1137/1.9781611975994.174}
  }
  

• [ bib ] Differentially Private Release of Synthetic Graphs
  with Marek Elias, Michael Kapralov, and Janardhan Kulkarni on SODA 2020
  

  A tight differentially private algorithm for releasing graphs with additive cut error

  @inproceedings{DBLP:conf/soda/EliasKKL20,
    author    = {Marek Eli{\'{a}}s and
                 Michael Kapralov and
                 Janardhan Kulkarni and
                 Yin Tat Lee},
    title     = {Differentially Private Release of Synthetic Graphs},
    booktitle = {Proceedings of the 2020 {ACM-SIAM} Symposium on Discrete Algorithms,
                 {SODA} 2020, Salt Lake City, UT, USA, January 5-8, 2020},
    pages     = {560--578},
    publisher = {{SIAM}},
    year      = {2020},
    url       = {https://doi.org/10.1137/1.9781611975994.34},
    doi       = {10.1137/1.9781611975994.34}
  }
  

• [ bib ] Chasing Nested Convex Bodies Nearly Optimally
  with Sebastien Bubeck, Boaz Klartag, Yuanzhi Li, and Mark Sellke on SODA 2020
  

  @inproceedings{DBLP:conf/soda/BubeckKLLS20,
    author    = {S{\'{e}}bastien Bubeck and
                 Bo'az Klartag and
                 Yin Tat Lee and
                 Yuanzhi Li and
                 Mark Sellke},
    title     = {Chasing Nested Convex Bodies Nearly Optimally},
    booktitle = {Proceedings of the 2020 {ACM-SIAM} Symposium on Discrete Algorithms,
                 {SODA} 2020, Salt Lake City, UT, USA, January 5-8, 2020},
    pages     = {1496--1508},
    publisher = {{SIAM}},
    year      = {2020},
    url       = {https://doi.org/10.1137/1.9781611975994.91},
    doi       = {10.1137/1.9781611975994.91}
  }
  

• [ bib ] A Generalized Central Limit Conjecture for Convex Bodies
  with Haotian Jiang and Santosh Vempala on GAFA Seminar Notes
  

  @article{jiang2020generalized,
    title={A Generalized Central Limit Conjecture for Convex Bodies},
    author={Jiang, Haotian and Lee, Yin Tat and Vempala, Santosh S},
    journal={Geometric Aspects of Functional Analysis},
    pages={1--41},
    year={2020},
    publisher={Springer}
  }
  

2019

• [ bib ] Complexity of Highly Parallel Non-Smooth Convex Optimization
  with Sebastien Bubeck, Qijia Jiang, Yuanzhi Li, and Aaron Sidford on NeurIPS 19
  

  @inproceedings{DBLP:conf/nips/BubeckJLLS19,
    author    = {S{\'{e}}bastien Bubeck and
                 Qijia Jiang and
                 Yin Tat Lee and
                 Yuanzhi Li and
                 Aaron Sidford},
    title     = {Complexity of Highly Parallel Non-Smooth Convex Optimization},
    booktitle = {Advances in Neural Information Processing Systems 32: Annual Conference
                 on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14
                 December 2019, Vancouver, BC, Canada},
    pages     = {13900--13909},
    year      = {2019},
    url       = {http://papers.nips.cc/paper/9541-complexity-of-highly-parallel-non-smooth-convex-optimization}
  }
  

• [ bib ] The Randomized Midpoint Method for Log-Concave Sampling
  with Ruoqi Shen on NeurIPS 2019
  

  @inproceedings{DBLP:conf/nips/ShenL19,
    author    = {Ruoqi Shen and
                 Yin Tat Lee},
    title     = {The Randomized Midpoint Method for Log-Concave Sampling},
    booktitle = {Advances in Neural Information Processing Systems 32: Annual Conference
                 on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14
                 December 2019, Vancouver, BC, Canada},
    pages     = {2098--2109},
    year      = {2019},
    url       = {http://papers.nips.cc/paper/8483-the-randomized-midpoint-method-for-log-concave-sampling}
  }
  

• [ bib ] Faster Matroid Intersection
  with Deeparnab Chakrabarty, Aaron Sidford, Sahil Singla, and Sam Chiu-wai Wong on FOCS 2019
  

  @inproceedings{DBLP:conf/focs/ChakrabartyLS0W19,
    author    = {Deeparnab Chakrabarty and
                 Yin Tat Lee and
                 Aaron Sidford and
                 Sahil Singla and
                 Sam Chiu{-}wai Wong},
    title     = {Faster Matroid Intersection},
    booktitle = {60th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
                 2019, Baltimore, Maryland, USA, November 9-12, 2019},
    pages     = {1146--1168},
    year      = {2019},
    url       = {https://doi.org/10.1109/FOCS.2019.00072},
    doi       = {10.1109/FOCS.2019.00072}
  }
  

• [ bib ] Competitively chasing convex bodies
  with Sebastien Bubeck, Yuanzhi Li, and Mark Sellke on STOC 2019
  

  See this and this for an almost tight bound.

  @inproceedings{DBLP:conf/stoc/BubeckLLS19,
    author    = {S{\'{e}}bastien Bubeck and
                 Yin Tat Lee and
                 Yuanzhi Li and
                 Mark Sellke},
    title     = {Competitively chasing convex bodies},
    booktitle = {Proceedings of the 51st Annual {ACM} {SIGACT} Symposium on Theory
                 of Computing, {STOC} 2019, Phoenix, AZ, USA, June 23-26, 2019.},
    pages     = {861--868},
    year      = {2019},
    url       = {https://doi.org/10.1145/3313276.3316314},
    doi       = {10.1145/3313276.3316314}
  }
  

• [ bib ] A near-optimal algorithm for approximating the John Ellipsoid
  with Michael Cohen, Ben Cousins, and Xin Yang on COLT 2019
  

  A practical algorithm for finding John Ellipsoid.

  @inproceedings{DBLP:conf/colt/CohenCLY19,
    author    = {Michael B. Cohen and
                 Ben Cousins and
                 Yin Tat Lee and
                 Xin Yang},
    title     = {A near-optimal algorithm for approximating the John Ellipsoid},
    booktitle = {Conference on Learning Theory, {COLT} 2019, 25-28 June 2019, Phoenix,
                 AZ, {USA}},
    pages     = {849--873},
    year      = {2019},
    url       = {http://proceedings.mlr.press/v99/cohen19a.html}
  }
  

• [ bib ] Near Optimal Methods for Minimizing Convex Functions with Lipschitz p-th Derivatives
  with GDGVSUJWZBJLS on COLT 2019
  

  @inproceedings{DBLP:conf/colt/GasnikovDGVSU0W19,
    author    = {Alexander Gasnikov and
                 Pavel Dvurechensky and
                 Eduard Gorbunov and
                 Evgeniya Vorontsova and
                 Daniil Selikhanovych and
                 C{\'{e}}sar A. Uribe and
                 Bo Jiang and
                 Haoyue Wang and
                 Shuzhong Zhang and
                 S{\'{e}}bastien Bubeck and
                 Qijia Jiang and
                 Yin Tat Lee and
                 Yuanzhi Li and
                 Aaron Sidford},
    title     = {Near Optimal Methods for Minimizing Convex Functions with Lipschitz
                 {\textdollar}p{\textdollar}-th Derivatives},
    booktitle = {Conference on Learning Theory, {COLT} 2019, 25-28 June 2019, Phoenix,
                 AZ, {USA}},
    pages     = {1392--1393},
    year      = {2019},
    url       = {http://proceedings.mlr.press/v99/gasnikov19b.html}
  }
  

• [ bib ] Solving Empirical Risk Minimization in the Current Matrix Multiplication Time
  with Zhao Song and Qiuyi Zhang on COLT 2019
  

  Many convex problems can be solved in matrix multiplication time now!

  @inproceedings{DBLP:conf/colt/LeeSZ19,
    author    = {Yin Tat Lee and
                 Zhao Song and
                 Qiuyi Zhang},
    title     = {Solving Empirical Risk Minimization in the Current Matrix Multiplication
                 Time},
    booktitle = {Conference on Learning Theory, {COLT} 2019, 25-28 June 2019, Phoenix,
                 AZ, {USA}},
    pages     = {2140--2157},
    year      = {2019},
    url       = {http://proceedings.mlr.press/v99/lee19a.html}
  }
  

• [ bib ] Adversarial examples from computational constraints
  with Sebastien Bubeck, Eric Price, and Ilya Razenshteyn on ICML 2019
  

  @inproceedings{DBLP:conf/icml/BubeckLPR19,
    author    = {S{\'{e}}bastien Bubeck and
                 Yin Tat Lee and
                 Eric Price and
                 Ilya P. Razenshteyn},
    title     = {Adversarial examples from computational constraints},
    booktitle = {Proceedings of the 36th International Conference on Machine Learning,
                 {ICML} 2019, 9-15 June 2019, Long Beach, California, {USA}},
    pages     = {831--840},
    year      = {2019},
    url       = {http://proceedings.mlr.press/v97/bubeck19a.html}
  }
  

• [ bib ] Metrical task systems on trees via mirror descent and unfair gluing
  with Sebastien Bubeck, Michael Cohen, and James R. Lee on SODA 2019
  

  @inproceedings{DBLP:conf/soda/BubeckCLL19,
    author    = {S{\'{e}}bastien Bubeck and
                 Michael B. Cohen and
                 James R. Lee and
                 Yin Tat Lee},
    title     = {Metrical task systems on trees via mirror descent and unfair gluing},
    booktitle = {Proceedings of the Thirtieth Annual {ACM-SIAM} Symposium on Discrete
                 Algorithms, {SODA} 2019, San Diego, California, USA, January 6-9,
                 2019},
    pages     = {89--97},
    year      = {2019},
    url       = {https://doi.org/10.1137/1.9781611975482.6},
    doi       = {10.1137/1.9781611975482.6}
  }
  

• [ bib ] A Nearly-Linear Bound for Chasing Nested Convex Bodies
  with C. J. Argue, Sebastien Bubeck, Michael Cohen, and Anupam Gupta on SODA 2019
  

  @inproceedings{DBLP:conf/soda/ArgueBCGL19,
    author    = {C. J. Argue and
                 S{\'{e}}bastien Bubeck and
                 Michael B. Cohen and
                 Anupam Gupta and
                 Yin Tat Lee},
    title     = {A Nearly-Linear Bound for Chasing Nested Convex Bodies},
    booktitle = {Proceedings of the Thirtieth Annual {ACM-SIAM} Symposium on Discrete
                 Algorithms, {SODA} 2019, San Diego, California, USA, January 6-9,
                 2019},
    pages     = {117--122},
    year      = {2019},
    url       = {https://doi.org/10.1137/1.9781611975482.8},
    doi       = {10.1137/1.9781611975482.8}
  }
  

2018

• [ bib ] Efficient Convex Optimization with Membership Oracles
  with Aaron Sidford and Santosh Vempala on COLT 2018
  

  @inproceedings{DBLP:conf/colt/LeeSV18,
    author    = {Yin Tat Lee and
                 Aaron Sidford and
                 Santosh S. Vempala},
    title     = {Efficient Convex Optimization with Membership Oracles},
    booktitle = {Conference On Learning Theory, {COLT} 2018, Stockholm, Sweden, 6-9
                 July 2018.},
    pages     = {1292--1294},
    year      = {2018},
    url       = {http://proceedings.mlr.press/v75/lee18a.html}
  }
  

• [ bib ] Universal Barrier is n-Self-Concordant
  with Man-Chung Yue on arXiv
  

  @article{DBLP:journals/mor/LeeY21,
    author    = {Yin Tat Lee and
                 Man{-}Chung Yue},
    title     = {Universal Barrier Is \emph{n}-Self-Concordant},
    journal   = {Math. Oper. Res.},
    volume    = {46},
    number    = {3},
    pages     = {1129--1148},
    year      = {2021},
    url       = {https://doi.org/10.1287/moor.2020.1113},
    doi       = {10.1287/moor.2020.1113}
  }
  

• [ bib ] The Paulsen problem, continuous operator scaling, and smoothed analysis
  with Tsz Chiu Kwok, Lap Chi Lau, and Akshay Ramachandran on STOC 2018
  

  Resolving the Paulsen problem, a major open problem in frame theory.

  @inproceedings{DBLP:conf/stoc/KwokLLR18,
    author    = {Tsz Chiu Kwok and
                 Lap Chi Lau and
                 Yin Tat Lee and
                 Akshay Ramachandran},
    title     = {The Paulsen problem, continuous operator scaling, and smoothed analysis},
    booktitle = {Proceedings of the 50th Annual {ACM} {SIGACT} Symposium on Theory
                 of Computing, {STOC} 2018, Los Angeles, CA, USA, June 25-29, 2018},
    pages     = {182--189},
    year      = {2018},
    url       = {http://doi.acm.org/10.1145/3188745.3188794},
    doi       = {10.1145/3188745.3188794}
  }
  

• [ bib ] A matrix expander Chernoff bound
  with Ankit Garg, Zhao Song, and Nikhil Srivastava on STOC 2018
  

  @inproceedings{DBLP:conf/stoc/GargLSS18,
    author    = {Ankit Garg and
                 Yin Tat Lee and
                 Zhao Song and
                 Nikhil Srivastava},
    title     = {A matrix expander Chernoff bound},
    booktitle = {Proceedings of the 50th Annual {ACM} {SIGACT} Symposium on Theory
                 of Computing, {STOC} 2018, Los Angeles, CA, USA, June 25-29, 2018},
    pages     = {1102--1114},
    year      = {2018},
    url       = {http://doi.acm.org/10.1145/3188745.3188890},
    doi       = {10.1145/3188745.3188890}
  }
  

• [ bib ] Stochastic localization + Stieltjes barrier = tight bound for log-Sobolev
  with Santosh Vempala on STOC 2018
  

  A tight estimate of the log-Sobolev constant for isotropic logconcave distributions.

  @inproceedings{DBLP:conf/stoc/LeeV18a,
    author    = {Yin Tat Lee and
                 Santosh S. Vempala},
    title     = {Stochastic localization + Stieltjes barrier = tight bound for log-Sobolev},
    booktitle = {Proceedings of the 50th Annual {ACM} {SIGACT} Symposium on Theory
                 of Computing, {STOC} 2018, Los Angeles, CA, USA, June 25-29, 2018},
    pages     = {1122--1129},
    year      = {2018},
    url       = {http://doi.acm.org/10.1145/3188745.3188866},
    doi       = {10.1145/3188745.3188866}
  }
  

• [ bib ] An homotopy method for lp regression provably beyond self-concordance and in input-sparsity time
  with Sebastien Bubeck, Michael Cohen, and Yuanzhi Li on STOC 2018
  

  First input-sparsity time algorithm for $l_p$ regression for $1 < p < \infty$.

  @inproceedings{DBLP:conf/stoc/BubeckCLL18,
    author    = {S{\'{e}}bastien Bubeck and
                 Michael B. Cohen and
                 Yin Tat Lee and
                 Yuanzhi Li},
    title     = {An homotopy method for lp regression provably beyond
                 self-concordance and in input-sparsity time},
    booktitle = {Proceedings of the 50th Annual {ACM} {SIGACT} Symposium on Theory
                 of Computing, {STOC} 2018, Los Angeles, CA, USA, June 25-29, 2018},
    pages     = {1130--1137},
    year      = {2018},
    url       = {http://doi.acm.org/10.1145/3188745.3188776},
    doi       = {10.1145/3188745.3188776}
  }
  

2017

• [ bib ] Optimal Algorithms for Smooth and Strongly Convex Distributed Optimization in Networks
  with Kevin Scaman, Francis Bach, and Sebastien Bubeck on ICML 2017
  

  @inproceedings{DBLP:conf/icml/ScamanBBLM17,
    author    = {Kevin Scaman and
                 Francis R. Bach and
                 S{\'{e}}bastien Bubeck and
                 Yin Tat Lee and
                 Laurent Massouli{\'{e}}},
    title     = {Optimal Algorithms for Smooth and Strongly Convex Distributed Optimization
                 in Networks},
    booktitle = {Proceedings of the 34th International Conference on Machine Learning,
                 {ICML} 2017, Sydney, NSW, Australia, 6-11 August 2017},
    pages     = {3027--3036},
    year      = {2017},
    url       = {http://proceedings.mlr.press/v70/scaman17a.html}
  }
  

• [ bib ] An SDP-based algorithm for linear-sized spectral sparsification
  with He Sun on STOC 2017
  

  First nearly-linear-time method for linear-sized spectral sparsification.

  @inproceedings{DBLP:conf/stoc/Lee017,
    author    = {Yin Tat Lee and
                 He Sun},
    title     = {An SDP-based algorithm for linear-sized spectral sparsification},
    booktitle = {Proceedings of the 49th Annual {ACM} {SIGACT} Symposium on Theory
                 of Computing, {STOC} 2017, Montreal, QC, Canada, June 19-23, 2017},
    pages     = {678--687},
    year      = {2017},
    url       = {http://doi.acm.org/10.1145/3055399.3055477},
    doi       = {10.1145/3055399.3055477}
  }
  

• [ bib ] Geodesic walks in polytopes
  with Santosh Vempala on STOC 2017
  

  First subquadratic-iterations method for sampling in polytopes.

  @inproceedings{DBLP:conf/stoc/LeeV17,
    author    = {Yin Tat Lee and
                 Santosh S. Vempala},
    title     = {Geodesic walks in polytopes},
    booktitle = {Proceedings of the 49th Annual {ACM} {SIGACT} Symposium on Theory
                 of Computing, {STOC} 2017, Montreal, QC, Canada, June 19-23, 2017},
    pages     = {927--940},
    year      = {2017},
    url       = {http://doi.acm.org/10.1145/3055399.3055416},
    doi       = {10.1145/3055399.3055416}
  }
  

• [ bib ] Subquadratic submodular function minimization
  with Deeparnab Chakrabarty, Aaron Sidford, and Sam Chiu-wai Wong on STOC 2017
  

  @inproceedings{DBLP:conf/stoc/ChakrabartyLSW17,
    author    = {Deeparnab Chakrabarty and
                 Yin Tat Lee and
                 Aaron Sidford and
                 Sam Chiu{-}wai Wong},
    title     = {Subquadratic submodular function minimization},
    booktitle = {Proceedings of the 49th Annual {ACM} {SIGACT} Symposium on Theory
                 of Computing, {STOC} 2017, Montreal, QC, Canada, June 19-23, 2017},
    pages     = {1220--1231},
    year      = {2017},
    url       = {http://doi.acm.org/10.1145/3055399.3055419},
    doi       = {10.1145/3055399.3055419}
  }
  

2016

• [ bib ] Black-box Optimization with a Politician
  with Sebastien Bubeck on ICML 2016
  

  @inproceedings{DBLP:conf/icml/BubeckL16,
    author    = {S{\'{e}}bastien Bubeck and
                 Yin Tat Lee},
    title     = {Black-box Optimization with a Politician},
    booktitle = {Proceedings of the 33nd International Conference on Machine Learning,
                 {ICML} 2016, New York City, NY, USA, June 19-24, 2016},
    pages     = {1624--1631},
    year      = {2016},
    url       = {http://jmlr.org/proceedings/data/v48/bubeck16.html}
  }
  

• [ bib ] Using Optimization to Obtain a Width-Independent, Parallel, Simpler, and Faster Positive SDP Solver
  with Zeyuan Allen Zhu and Lorenzo Orecchia on SODA 2016
  

  @inproceedings{DBLP:conf/soda/Allen-ZhuLO16,
    author    = {Zeyuan {Allen Zhu} and
                 Yin Tat Lee and
                 Lorenzo Orecchia},
    title     = {Using Optimization to Obtain a Width-Independent, Parallel, Simpler,
                 and Faster Positive {SDP} Solver},
    booktitle = {Proceedings of the Twenty-Seventh Annual {ACM-SIAM} Symposium on Discrete
                 Algorithms, {SODA} 2016, Arlington, VA, USA, January 10-12, 2016},
    pages     = {1824--1831},
    year      = {2016},
    url       = {https://doi.org/10.1137/1.9781611974331.ch127},
    doi       = {10.1137/1.9781611974331.ch127}
  }
  

• [ bib ] Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile
  with Tsz Chiu Kwok and Lap Chi Lau on SODA 2016
  

  @article{DBLP:journals/siamcomp/KwokLL17,
    author    = {Tsz Chiu Kwok and
                 Lap Chi Lau and
                 Yin Tat Lee},
    title     = {Improved Cheeger's Inequality and Analysis of Local Graph Partitioning
                 using Vertex Expansion and Expansion Profile},
    journal   = {{SIAM} J. Comput.},
    volume    = {46},
    number    = {3},
    pages     = {890--910},
    year      = {2017},
    url       = {https://doi.org/10.1137/16M1079816},
    doi       = {10.1137/16M1079816}
  }
  

• [ bib ] Geometric median in nearly linear time
  with Michael Cohen, Gary Miller, Jakub Pachocki, and Aaron Sidford on STOC 2016
  

  @inproceedings{DBLP:conf/stoc/CohenLMPS16,
    author    = {Michael B. Cohen and
                 Yin Tat Lee and
                 Gary L. Miller and
                 Jakub Pachocki and
                 Aaron Sidford},
    title     = {Geometric median in nearly linear time},
    booktitle = {Proceedings of the 48th Annual {ACM} {SIGACT} Symposium on Theory
                 of Computing, {STOC} 2016, Cambridge, MA, USA, June 18-21, 2016},
    pages     = {9--21},
    year      = {2016},
    url       = {http://doi.acm.org/10.1145/2897518.2897647},
    doi       = {10.1145/2897518.2897647}
  }
  

• [ bib ] Sparsified Cholesky and multigrid solvers for connection laplacians
  with Rasmus Kyng, Richard Peng, Sushant Sachdeva, and Daniel Spielman on STOC 2016
  

  A variant Multigrid and Cholesky Decomposition that runs in nearly linear time for any SDD matrices. Simplified for sequential case.

  @inproceedings{DBLP:conf/stoc/KyngLPSS16,
    author    = {Rasmus Kyng and
                 Yin Tat Lee and
                 Richard Peng and
                 Sushant Sachdeva and
                 Daniel A. Spielman},
    title     = {Sparsified Cholesky and multigrid solvers for connection laplacians},
    booktitle = {Proceedings of the 48th Annual {ACM} {SIGACT} Symposium on Theory
                 of Computing, {STOC} 2016, Cambridge, MA, USA, June 18-21, 2016},
    pages     = {842--850},
    year      = {2016},
    url       = {http://doi.acm.org/10.1145/2897518.2897640},
    doi       = {10.1145/2897518.2897640}
  }
  

• [ bib ] Landmark-Matching Transformation with Large Deformation Via n-dimensional Quasi-conformal Maps
  with Ka Chun Lam and Lok Ming Lui on J. Sci. Comput.
  

  @article{DBLP:journals/jscic/LeeLL16,
    author    = {Yin Tat Lee and
                 Ka Chun Lam and
                 Lok Ming Lui},
    title     = {Landmark-Matching Transformation with Large Deformation Via n-dimensional
                 Quasi-conformal Maps},
    journal   = {J. Sci. Comput.},
    volume    = {67},
    number    = {3},
    pages     = {926--954},
    year      = {2016},
    url       = {https://doi.org/10.1007/s10915-015-0113-5},
    doi       = {10.1007/s10915-015-0113-5}
  }
  

2015

• [ bib ] A geometric alternative to Nesterov's accelerated gradient descent
  with Sebastien Bubeck and Mohit Singh on arXiv
  

  A variant of Ellipsoid method that works really well.

  @article{DBLP:journals/corr/BubeckLS15,
    author    = {S{\'{e}}bastien Bubeck and
                 Yin Tat Lee and
                 Mohit Singh},
    title     = {A geometric alternative to Nesterov's accelerated gradient descent},
    journal   = {CoRR},
    volume    = {abs/1506.08187},
    year      = {2015},
    url       = {http://arxiv.org/abs/1506.08187},
    archivePrefix = {arXiv},
    eprint    = {1506.08187}
  }
  

• [ bib ] Efficient Inverse Maintenance and Faster Algorithms for Linear Programming
  with Aaron Sidford on FOCS 2015
  

  Each iteration of interior point method takes $O(\mathrm{nnz}(A)+\mathrm{rank}(A)^2)$.

  @inproceedings{DBLP:conf/focs/LeeS15,
    author    = {Yin Tat Lee and
                 Aaron Sidford},
    title     = {Efficient Inverse Maintenance and Faster Algorithms for Linear Programming},
    booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS}
                 2015, Berkeley, CA, USA, 17-20 October, 2015},
    pages     = {230--249},
    year      = {2015},
    url       = {https://doi.org/10.1109/FOCS.2015.23},
    doi       = {10.1109/FOCS.2015.23}
  }
  

• [ bib ] Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time
  with He Sun on FOCS 2015, SIAM J. Comput.
  

  Improved to nearly-linear-time.

  @article{DBLP:journals/siamcomp/Lee018,
    author    = {Yin Tat Lee and
                 He Sun},
    title     = {Constructing Linear-Sized Spectral Sparsification in Almost-Linear
                 Time},
    journal   = {{SIAM} J. Comput.},
    volume    = {47},
    number    = {6},
    pages     = {2315--2336},
    year      = {2018},
    url       = {https://doi.org/10.1137/16M1061850},
    doi       = {10.1137/16M1061850}
  }
  

• [ bib ] Uniform Sampling for Matrix Approximation
  with Michael Cohen, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford on ITCS 2015
  

  Solving a system of a tall matrix is as easy as a square matrix.

  @inproceedings{DBLP:conf/innovations/CohenLMMPS15,
    author    = {Michael B. Cohen and
                 Yin Tat Lee and
                 Cameron Musco and
                 Christopher Musco and
                 Richard Peng and
                 Aaron Sidford},
    title     = {Uniform Sampling for Matrix Approximation},
    booktitle = {Proceedings of the 2015 Conference on Innovations in Theoretical Computer
                 Science, {ITCS} 2015, Rehovot, Israel, January 11-13, 2015},
    pages     = {181--190},
    year      = {2015},
    url       = {http://doi.acm.org/10.1145/2688073.2688113},
    doi       = {10.1145/2688073.2688113}
  }
  

2014

• [ bib ] Single Pass Spectral Sparsification in Dynamic Streams
  with Michael Kapralov, Cameron Musco, Christopher Musco, and Aaron Sidford on FOCS 2014, SIAM J. Comput.
  

  @article{DBLP:journals/siamcomp/KLMMS17,
    author    = {Michael Kapralov and
                 Yin Tat Lee and
                 Cameron Musco and
                 Christopher Musco and
                 Aaron Sidford},
    title     = {Single Pass Spectral Sparsification in Dynamic Streams},
    journal   = {{SIAM} J. Comput.},
    volume    = {46},
    number    = {1},
    pages     = {456--477},
    year      = {2017},
    url       = {https://doi.org/10.1137/141002281},
    doi       = {10.1137/141002281},
    timestamp = {Sat, 27 May 2017 14:22:59 +0200},
    biburl    = {https://dblp.org/rec/bib/journals/siamcomp/KapralovLMMS17},
    bibsource = {dblp computer science bibliography, https://dblp.org}
  }
  

2013

• [ bib ] Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems
  with Aaron Sidford on FOCS 2013
  

  First efficient version of accelerated coordinate descent methods. Improved.

  @inproceedings{DBLP:conf/focs/LeeS13,
    author    = {Yin Tat Lee and
                 Aaron Sidford},
    title     = {Efficient Accelerated Coordinate Descent Methods and Faster Algorithms
                 for Solving Linear Systems},
    booktitle = {54th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
                 2013, 26-29 October, 2013, Berkeley, CA, {USA}},
    pages     = {147--156},
    year      = {2013},
    url       = {https://doi.org/10.1109/FOCS.2013.24},
    doi       = {10.1109/FOCS.2013.24}
  }
  

• [ bib ] Improved Cheeger's inequality: analysis of spectral partitioning algorithms
  with Tsz Chiu Kwok, Lap Chi Lau, Shayan Oveis Gharan, and Luca Trevisan on STOC 2013, SIAM J. Comput.
  

  Proving that Cheeger’s inequality is tight for graphs with spectral gaps.

  @inproceedings{DBLP:conf/stoc/KwokLLGT13,
    author    = {Tsz Chiu Kwok and
                 Lap Chi Lau and
                 Yin Tat Lee and
                 Shayan Oveis Gharan and
                 Luca Trevisan},
    title     = {Improved Cheeger's inequality: analysis of spectral partitioning algorithms
                 through higher order spectral gap},
    booktitle = {Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA,
                 USA, June 1-4, 2013},
    pages     = {11--20},
    year      = {2013},
    url       = {http://doi.acm.org/10.1145/2488608.2488611},
    doi       = {10.1145/2488608.2488611}
  }
  

• [ bib ] A new approach to computing maximum flows using electrical flows
  with Satish Rao, Nikhil Srivastava on STOC 2013
  

  Improved to nearly-linear-time.

  @inproceedings{DBLP:conf/stoc/LeeRS13,
    author    = {Yin Tat Lee and
                 Satish Rao and
                 Nikhil Srivastava},
    title     = {A new approach to computing maximum flows using electrical flows},
    booktitle = {Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA,
                 USA, June 1-4, 2013},
    pages     = {755--764},
    year      = {2013},
    url       = {http://doi.acm.org/10.1145/2488608.2488704},
    doi       = {10.1145/2488608.2488704}
  }