Yin Tat Lee

Orcid: 0000-0002-4692-5442

According to our database1, Yin Tat Lee authored at least 117 papers between 2013 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

On csauthors.net:

Bibliography

2024
Short-step methods are not strongly polynomial-time.
Math. Program., September, 2024

Phi-3 Technical Report: A Highly Capable Language Model Locally on Your Phone.
CoRR, 2024

Improving the Bit Complexity of Communication for Distributed Convex Optimization.
Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Convex Minimization with Integer Minima in <i>Õ</i>(<i>n</i><sup>4</sup>) Time.
Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Differentially Private Synthetic Data via Foundation Model APIs 2: Text.
Proceedings of the Forty-first International Conference on Machine Learning, 2024

2023
Can Generalist Foundation Models Outcompete Special-Purpose Tuning? Case Study in Medicine.
CoRR, 2023

Positional Description Matters for Transformers Arithmetic.
CoRR, 2023

Textbooks Are All You Need II: phi-1.5 technical report.
CoRR, 2023

Textbooks Are All You Need.
CoRR, 2023

An Empirical Study on Challenging Math Problem Solving with GPT-4.
CoRR, 2023

Convex Minimization with Integer Minima in Õ(n<sup>4</sup>) Time.
CoRR, 2023

Sparks of Artificial General Intelligence: Early experiments with GPT-4.
CoRR, 2023

kNN-Adapter: Efficient Domain Adaptation for Black-Box Language Models.
CoRR, 2023

Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method.
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Private Convex Optimization in General Norms.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Learning threshold neurons via edge of stability.
Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Exploring the Limits of Differentially Private Deep Learning with Group-wise Clipping.
Proceedings of the Eleventh International Conference on Learning Representations, 2023

ReSQueing Parallel and Private Stochastic Convex Optimization.
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Automatic Prompt Optimization with "Gradient Descent" and Beam Search.
Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, 2023

Condition-number-independent Convergence Rate of Riemannian Hamiltonian Monte Carlo with Numerical Integrators.
Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Sampler.
Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022
Geodesic Walks in Polytopes.
SIAM J. Comput., 2022

A Slightly Improved Bound for the KLS Constant.
CoRR, 2022

Faster maxflow via improved dynamic spectral vertex sparsifiers.
Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Computing Lewis Weights to High Precision.
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time.
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

When Does Differentially Private Learning Not Suffer in High Dimensions?
Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Sampling with Riemannian Hamiltonian Monte Carlo in a Constrained Space.
Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexity.
Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensions.
Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Differentially Private Fine-tuning of Language Models.
Proceedings of the Tenth International Conference on Learning Representations, 2022

The Manifold Joys of Sampling (Invited Talk).
Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Private Convex Optimization via Exponential Mechanism.
Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

2021
Metrical Task Systems on Trees via Mirror Descent and Unfair Gluing.
SIAM J. Comput., 2021

Universal Barrier Is <i>n</i>-Self-Concordant.
Math. Oper. Res., 2021

Solving Linear Programs in the Current Matrix Multiplication Time.
J. ACM, 2021

Kernel-based Methods for Bandit Convex Optimization.
J. ACM, 2021

Tutorial on the Robust Interior Point Method.
CoRR, 2021

Private Non-smooth Empirical Risk Minimization and Stochastic Convex Optimization in Subquadratic Steps.
CoRR, 2021

Reducing isotropy and volume to KLS: an <i>o</i>*(<i>n</i><sup>3</sup><i>ψ</i><sup>2</sup>) volume algorithm.
Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central path.
Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Minimum cost flows, MDPs, and ℓ<sub>1</sub>-regression in nearly linear time for dense instances.
Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions.
Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Private Non-smooth ERM and SCO in Subquadratic Steps.
Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Numerical Composition of Differential Privacy.
Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Fast and Memory Efficient Differentially Private-SGD via JL Projections.
Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Structured Logconcave Sampling with a Restricted Gaussian Oracle.
Proceedings of the Conference on Learning Theory, 2021

2020
Introduction to the Special Issue on SODA'18.
ACM Trans. Algorithms, 2020

Reducing Isotropy and Volume to KLS: An O(n<sup>3</sup>ψ<sup>2</sup>) Volume Algorithm.
CoRR, 2020

Composite Logconcave Sampling with a Restricted Gaussian Oracle.
CoRR, 2020

Network size and weights size for memorization with two-layers neural networks.
CoRR, 2020

Strong self-concordance and sampling.
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

An improved cutting plane method for convex optimization, convex-concave games, and its applications.
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Positive semidefinite programming: mixed, parallel, and width-independent.
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Solving tall dense linear programs in nearly linear time.
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Differentially Private Release of Synthetic Graphs.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Computing Circle Packing Representations of Planar Graphs.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Chasing Nested Convex Bodies Nearly Optimally.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Acceleration with a Ball Optimization Oracle.
Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Network size and size of the weights in memorization with two-layers neural networks.
Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Convex Optimization and Dynamic Data Structure (Invited Talk).
Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2020

A Faster Interior Point Method for Semidefinite Programming.
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs.
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo.
Proceedings of the Conference on Learning Theory, 2020

An $\widetilde\mathcalO(m/\varepsilon^3.5)$-Cost Algorithm for Semidefinite Programs with Diagonal Constraints.
Proceedings of the Conference on Learning Theory, 2020

Leverage Score Sampling for Faster Accelerated Regression and ERM.
Proceedings of the Algorithmic Learning Theory, 2020

2019
Optimal Convergence Rates for Convex Distributed Optimization in Networks.
J. Mach. Learn. Res., 2019

Solving Linear Programs with Sqrt(rank) Linear System Solves.
CoRR, 2019

An Õ(m/ε<sup>3.5</sup>)-Cost Algorithm for Semidefinite Programs with Diagonal Constraints.
CoRR, 2019

Competitively chasing convex bodies.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

A Nearly-Linear Bound for Chasing Nested Convex Bodies.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

The Randomized Midpoint Method for Log-Concave Sampling.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Complexity of Highly Parallel Non-Smooth Convex Optimization.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Adversarial examples from computational constraints.
Proceedings of the 36th International Conference on Machine Learning, 2019

Faster Matroid Intersection.
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Solving Empirical Risk Minimization in the Current Matrix Multiplication Time.
Proceedings of the Conference on Learning Theory, 2019

Near Optimal Methods for Minimizing Convex Functions with Lipschitz $p$-th Derivatives.
Proceedings of the Conference on Learning Theory, 2019

A near-optimal algorithm for approximating the John Ellipsoid.
Proceedings of the Conference on Learning Theory, 2019

Near-optimal method for highly smooth convex optimization.
Proceedings of the Conference on Learning Theory, 2019

2018
Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time.
SIAM J. Comput., 2018

Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities.
CoRR, 2018

Adversarial Examples from Cryptographic Pseudo-Random Generators.
CoRR, 2018

Chasing Nested Convex Bodies Nearly Optimally.
CoRR, 2018

The Kannan-Lovász-Simonovits Conjecture.
CoRR, 2018

Stochastic localization + Stieltjes barrier = tight bound for log-Sobolev.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Convergence rate of riemannian Hamiltonian Monte Carlo and faster polytope volume computation.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

The Paulsen problem, continuous operator scaling, and smoothed analysis.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

A matrix expander Chernoff bound.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

k-server via multiscale entropic regularization.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

An homotopy method for l<sub>p</sub> regression provably beyond self-concordance and in input-sparsity time.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Optimal Algorithms for Non-Smooth Distributed Optimization in Networks.
Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Efficient Convex Optimization with Membership Oracles.
Proceedings of the Conference On Learning Theory, 2018

2017
Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile.
SIAM J. Comput., 2017

Single Pass Spectral Sparsification in Dynamic Streams.
SIAM J. Comput., 2017

An SDP-based algorithm for linear-sized spectral sparsification.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Subquadratic submodular function minimization.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Optimal Algorithms for Smooth and Strongly Convex Distributed Optimization in Networks.
Proceedings of the 34th International Conference on Machine Learning, 2017

Eldan's Stochastic Localization and the KLS Hyperplane Conjecture: An Improved Lower Bound for Expansion.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016
Landmark-Matching Transformation with Large Deformation Via n-dimensional Quasi-conformal Maps.
J. Sci. Comput., 2016

Sparsified Cholesky and multigrid solvers for connection laplacians.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Geometric median in nearly linear time.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Using Optimization to Obtain a Width-Independent, Parallel, Simpler, and Faster Positive SDP Solver.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Black-box Optimization with a Politician.
Proceedings of the 33nd International Conference on Machine Learning, 2016

2015
Sparsified Cholesky Solvers for SDD linear systems.
CoRR, 2015

A geometric alternative to Nesterov's accelerated gradient descent.
CoRR, 2015

Uniform Sampling for Matrix Approximation.
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Efficient Inverse Maintenance and Faster Algorithms for Linear Programming.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014
Large Deformation Registration via n-dimensional Quasi-conformal Maps.
CoRR, 2014

Probabilistic Spectral Sparsification In Sublinear Time.
CoRR, 2014

An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Path Finding Methods for Linear Programming: Solving Linear Programs in Õ(vrank) Iterations and Faster Algorithms for Maximum Flow.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013
Following the Path of Least Resistance : An Õ(m sqrt(n)) Algorithm for the Minimum Cost Flow Problem.
CoRR, 2013

Matching the Universal Barrier Without Paying the Costs : Solving Linear Programs with Õ(sqrt(rank)) Linear System Solves.
CoRR, 2013

A new approach to computing maximum flows using electrical flows.
Proceedings of the Symposium on Theory of Computing Conference, 2013

Improved Cheeger's inequality: analysis of spectral partitioning algorithms through higher order spectral gap.
Proceedings of the Symposium on Theory of Computing Conference, 2013

Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013


  Loading...