معرفی
Nathan Klein is an Assistant Professor in the Department of Computer Science at Boston University, part of the College of Arts & Sciences. His research focuses on designing fast approximation algorithms for computationally challenging problems, particularly the Traveling Salesperson Problem (TSP), employing tools from combinatorics, probability, and polynomial theory. He earned his PhD from the University of Washington in 2023 and was a postdoctoral researcher at the Institute for Advanced Study before joining BU in 2024.
Education: PhD in Computer Science from the University of Washington (2023), advised by Anna Karlin and Shayan Oveis Gharan. Postdoctoral work at the Institute for Advanced Study.
Research Interests: Approximation algorithms for graph problems, rounding techniques, and the application of polynomial methods. His work emphasizes translating continuous solutions into discrete ones, particularly for TSP variants and edge-connectivity problems.
Key Contributions: Improved approximation algorithms for TSP and prize-collecting TSP, analysis of the max entropy algorithm, and work on k-edge-connectivity rounding. His research bridges theoretical computer science with practical algorithm design.
Scientific Awards: Best Paper Award at STOC 2021 for contributions to TSP approximation.
Advising & Grants: Advising postdoc Zhuan Khye Koh. Involved in grants related to algorithmic improvements and approximation methods. Teaching courses like Advanced Algorithms and Rounding Techniques in Approximation Algorithms.
Labs/Teams: Active in Boston University's theoretical computer science group, focusing on algorithmic foundations and optimization.
