All papers:

• Ghost Value Augmentation for \(k\)-Edge-Connectivity
  D. Ellis Hershkowitz, N. Klein, R. Zenklusen
  STOC 2024

• From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP
  L. Gurvits, N. Klein, J. Leake
  ICALP 2024

• A Lower Bound for the Max Entropy Algorithm for TSP
  B. Jin, N. Klein, D. Williamson
  IPCO 2024

• A Better-Than-1.6-Approximation for Prize-Collecting TSP
  J. Blauth, N. Klein, M. Nägele
  IPCO 2024

• 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

• 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)

• Symmetric-Key Broadcast Encryption: The Multi-Sender Case
  C. Freitag, J. Katz, N. Klein
  CSCML 2017

• On the Approximability of DAG Edge Deletion
  N. Klein and T. Wexler
  Undergraduate thesis, 2016

• New Features for Duplicate Bug Detection
  N. Klein, C.S. Corley, and N.A. Kraft
  MSR 2014