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.

**Papers:**

- A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP

A. Karlin, N. Klein, S. Oveis Gharan, 2021

- An Improved Approximation Algorithm for the Minimum k-Edge Connected Multi-Subgraph Problem

A. Karlin, N. Klein, S. Oveis Gharan, X. Zhang, 2021

- A (Slightly) Improved Approximation Algorithm for Metric TSP

A. Karlin, N. Klein, S. Oveis Gharan*STOC 2021*

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)

- Symmetric-Key Broadcast Encryption: The Multi-Sender Case

C. Freitag, J. Katz, N. Klein*CSCML 2017*

- New Features for Duplicate Bug Detection

N. Klein, C.S. Corley, and N.A. Kraft*MSR 2014*

**Manuscripts:**

- On the Approximability of DAG Edge Deletion

N. Klein and T. Wexler

Undergraduate thesis, 2016

**Other writing:**

**Concerning waffles:** the correct recipe

## Contact

Email: nathan dot klein711 at gmail dot com