I'm a postdoc in the School of Mathematics at the Institute for Advanced Study. I recently finished my PhD at the University of Washington, where I was advised by Anna Karlin and Shayan Oveis Gharan.
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 joining Boston University as an Assistant Professor in the summer of 2024. I will be looking for students, so 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):
- Ghost Value Augmentation for k-ECSS and k-ECSM
D. Ellis Hershkowitz, N. Klein, R. Zenklusen
2023
- From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP
L. Gurvits, N. Klein, J. Leake
2023
- A Lower Bound for the Max Entropy Algorithm for TSP
B. Jin, N. Klein, D. Williamson
2023
- A Better-Than-1.6-Approximation for Prize-Collecting TSP
J. Blauth, N. Klein, M. Nägele
2023
- Thin Trees for Laminar Families
N. Klein and N. Olver
FOCS 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)
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