I'm a PhD student at the University of Washington where I am advised by Anna Karlin and Shayan Oveis Gharan. I graduated from Oberlin College and Conservatory in 2016 and spent some time in industry before coming to UW in 2018.
I mainly study approximation algorithms. Recently I have been using ideas from combinatorics and the geometry of polynomials to help analyze algorithms for TSP and other optimization problems. Here is my CV.
I will be at the Institute for Advanced Study for the 2023 - 2024 academic year and then will be joining Boston University as an Assistant Professor in the summer of 2024. I will be looking for students starting in 2024. If you are interested, apply to BU this fall and feel free to reach out. We have a strong and growing theory group and are a part of Boston's vibrant academic community.
Recent papers (all):
- Thin Trees for Laminar Families
N. Klein and N. Olver
2023
- A (Slightly) Improved Deterministic Approximation Algorithm for Metric TSP
A. Karlin, N. Klein, S. Oveis Gharan
IPCO 2023
- A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP
B. Jin, N. Klein, D. Williamson
IPCO 2023
- Matroid Partition Property and the Secretary Problem
D. Abdolazimi, A. Karlin, N. Klein, S. Oveis Gharan
ITCS 2023
- A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP
A. Karlin, N. Klein, S. Oveis Gharan
FOCS 2022
ICERM talk (structure of near min cuts)
- An Improved Approximation Algorithm for the Minimum k-Edge Connected Multi-Subgraph Problem
A. Karlin, N. Klein, S. Oveis Gharan, X. Zhang
STOC 2022
- A (Slightly) Improved Approximation Algorithm for Metric TSP (journal version)
A. Karlin, N. Klein, S. Oveis Gharan
STOC 2021 (Best paper award)
APPROX 2020 invited talk (a high level overview)
IGAFIT colloquium (slightly less technical overview)
Geometry of Polynomials talk (focuses more on Strongly Rayleigh distributions)
- An Improved Approximation Algorithm for TSP in the Half Integral Case
A. Karlin, N. Klein, S. Oveis Gharan
STOC 2020
TCS+ talk (long version), STOC talk (shorter version)
Other writing: a short article on approximating TSP (for the general public)
Misc: concerning waffles / concerning primes / concerning math gamesContact
Email: nathan dot klein711 at gmail dot com