Best 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 A. 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}
    }
    

Surveys

  • [ bib ] The Kannan-Lovász-Simonovits Conjecture
    with Santosh S. 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 ] k-server via multiscale entropic regularization
    with Sebastien Bubeck, Michael B. Cohen, James R. 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 S. 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}
    }
    
  • [ 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}
    }
    

Other Publications

2018

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

    Here is the computer assisted proof.

    @article{DBLP:journals/corr/LeeY18,
      author    = {Yin Tat Lee and
                   Man-Chung Yue},
      title     = {Universal Barrier is n-Self-Concordant},
      journal   = {CoRR},
      volume    = {abs/1809.03011},
      year      = {2018},
      url       = {https://arxiv.org/abs/1809.03011},
      archivePrefix = {arXiv},
      eprint    = {1809.03011}
    }
    
  • [ 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 S. 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 B. 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 R. 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 S. 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 B. Cohen, Gary L. 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 A. 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

    Improved to nearly-linear-time.

    @inproceedings{DBLP:conf/focs/LeeS15a,
      author    = {Yin Tat Lee and
                   He Sun},
      title     = {Constructing Linear-Sized Spectral Sparsification in Almost-Linear
                   Time},
      booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS}
                   2015, Berkeley, CA, USA, 17-20 October, 2015},
      pages     = {250--269},
      year      = {2015},
      url       = {https://doi.org/10.1109/FOCS.2015.24},
      doi       = {10.1109/FOCS.2015.24}
    }
    
  • [ bib ] Uniform Sampling for Matrix Approximation
    with Michael B. 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 ] 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}
    }