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 am currently looking for faculty positions.
Recent papers (all):
- 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
- 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
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