Re: [theory students] Theory Students Meeting with Faculty Candidate Nathan Klein

[Matt Sinclair <sinclair@xxxxxxxxxxx>]

Hi all,

I just wanted to check on this again, as I didn't hear back from anyone who said they were interested/able to do it.

Thanks,

Matt

---

From: Matt Sinclair
Sent: Wednesday, February 15, 2023 5:45 PM
To: theory-students@xxxxxxxxxxx <theory-students@xxxxxxxxxxx>
Subject: RE: Theory Students Meeting with Faculty Candidate Nathan Klein

 

Sorry for the double-email, I forgot to include the details about Nathan.  Here they are:

 

Who: Nathan Klein

 

Bio: Nathan Klein is a final year Ph.D. student at the University of Washington where he is advised by Anna Karlin and Shayan Oveis Gharan. His primary research interest is studying approximation algorithms for classical optimization problems. He has received a best paper award at STOC 2021 and an NSF GRFP fellowship for his work on the traveling salesperson problem.

 

Website: https://homes.cs.washington.edu/~nwklein/

 

Talk Title: A (Slightly) Improved Approximation Algorithm for Metric TSP

Abstract: In the metric traveling salesperson problem (TSP) we are given a list of cities and their pairwise symmetric distances, which form a metric. Our goal is to find the shortest tour that visits every city exactly once. The problem is NP-Hard, and therefore it is unlikely that an efficient algorithm exists which can solve it exactly. However, in 1976 Christofides gave a beautiful 3/2 approximation algorithm for the problem, meaning a polynomial time algorithm which provably returns a tour at most 50% longer than the optimal one. This algorithm is one of the first approximation algorithms ever designed and is routinely used in practice for planning and routing tasks. In this talk I will describe an approximation algorithm for TSP with approximation ratio below 3/2, representing the first improvement in nearly half a century.

 

From: Matt Sinclair
Sent: Wednesday, February 15, 2023 5:44 PM
To: theory-students@xxxxxxxxxxx
Subject: Theory Students Meeting with Faculty Candidate Nathan Klein

 

Hi all,

 

My name is Matt Sinclair and I’m an Assistant Professor here.  I’ll be hosting faculty candidate Nathan Klein (details below) April 18^th – 19^th.  As part of his interview, Nathan has requested a meeting with the current Theory students (you all!).  Thus, I wanted to reach out and see if a small group of you would be willing to help organize such a meeting?  We have two choices for it:

 

1. A small group of you (~3) could take Nathan to lunch one day during his interview or
2. We could have an hour-long meeting either Tuesday or Wednesday (not during a meal) where more of you could join.

 

I’d like to nail this piece down relatively soon, since other people will be signing up and it will be better to have a clear idea of when you all may be available to meet with Nathan.  So, please let me know if this is something you are interested in by next week Wednesday, 2/22/23.  Likewise, please let me know if you are interested in helping coordinate this meeting with other Theory students.

 

Thanks!

Matt