UW CSE’s Shayan Oveis Gharan has received an NSF CAREER Award – the 29th UW CSE faculty member to have been recognized through this program and its predecessors.
The NSF CAREER Program “offers the National Science Foundation’s most prestigious awards in support of junior faculty who exemplify the role of teacher-scholars through outstanding research, excellent education and the integration of education and research.”
Shayan is one of the most recent additions to UW CSE’s Theoretical Computer Science Group. His research focuses on the design and analysis of algorithms. With his coauthors, he gave the first asymptotic improvement in the approximation ratio for the Asymmetric Traveling Salesman Problem (TSP) in over 30 years, for which he won the best paper award at SODA 2010. He followed this up by doing the same for the standard TSP problem on graphs, improving Christofides’ famous 3/2 bound from 1976; for that, he won the best paper award at FOCS 2011. Most recently, by proving a generalization of the famous Kadison-Singer Conjecture, Shayan and Nima Amari have given an improved bound on the integrality gap of the classical Held-Karp relaxation for Asymmetric TSP. In addition to his work in approximation algorithms, Shayan is well-known for fundamental contributions in algorithmic spectral graph theory.
Congratulations Shayan!