| 2026 | ICALP | Thin Trees for near Minimum Cuts. | Nathan Klein, Neil Olver, Zi Song Yeoh |
| 2026 | STOC | A Strong Linear Programming Relaxation for Weighted Tree Augmentation. | Vincent Cohen-Addad, Marina Drygala, Nathan Klein, Ola Svensson |
| 2024 | ICALP | From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP. | Leonid Gurvits, Nathan Klein, Jonathan Leake |
| 2024 | IPCO | A Better-Than-1.6-Approximation for Prize-Collecting TSP. | Jannis Blauth, Nathan Klein, Martin Ngele |
| 2024 | IPCO | A Lower Bound for the Max Entropy Algorithm for TSP. | Billy Jin, Nathan Klein, David P. Williamson |
| 2024 | STOC | Ghost Value Augmentation for k-Edge-Connectivity. | D. Ellis Hershkowitz, Nathan Klein, Rico Zenklusen |
| 2023 | FOCS | Thin Trees for Laminar Families. | Nathan Klein, Neil Olver |
| 2023 | IPCO | A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP. | Billy Jin, Nathan Klein, David P. Williamson |
| 2023 | IPCO | A Deterministic Better-than-3/2 Approximation Algorithm for Metric TSP. | Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan |
| 2022 | FOCS | A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP. | Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan |
| 2022 | STOC | An improved approximation algorithm for the minimum | Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan, Xinzhi Zhang |
| 2021 | STOC | A (slightly) improved approximation algorithm for metric TSP. | Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan |
| 2020 | STOC | An improved approximation algorithm for TSP in the half integral case. | Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan |
| 2014 | MSR | New features for duplicate bug detection. | Nathan Klein, Christopher S. Corley, Nicholas A. Kraft |
| 2008 | WSC | Feasibility study for replacing the MK19 automatic grenade launching system. | Kyle Hurst, Nathan Klein, Mario Feliciano, Steven Warner, Scott Crino |