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 games

## Contact

Email: nathan dot klein711 at gmail dot com