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