Shayan Oveis Gharan

Shayan Oveis Gharan is the Lazowska Professor of Computer Science & Engineering at the Paul Allen School of Computer Science and Engineering, University of Washington. His research focuses on the design and analysis of algorithms using algebraic techniques, particularly through the lens of spectral graph theory and polynomial methods.

He received his PhD from the Management Science and Engineering department at Stanford University in 2013, where his thesis won an ACM Doctoral Dissertation Award Honorable Mention. Before joining the University of Washington, he was a Miller Fellow at UC Berkeley for one and a half years.

His research interests span algorithms, spectral graph theory, log-concave and real stable polynomials, and their applications to combinatorial optimization. His work has established deep connections between algebraic properties of polynomials and algorithmic problems, particularly in approximation algorithms and counting/sampling problems. He has made significant contributions to the Traveling Salesman Problem, matroid theory, and high-dimensional expanders.

Oveis Gharan's recent publications reveal a strong focus on polynomial methods applied to combinatorial structures. His work on log-concave polynomials has led to breakthroughs in sampling and counting algorithms, while his research on spectral graph theory has produced improved approximation algorithms for fundamental optimization problems like the Traveling Salesman Problem.

Major awards and honors:

• 2025 Michael and Sheila Held Prize
• 2024 Lazowska Endowed Professorship
• 2023 Smale Prize
• 2022 Simons Investigator Award
• 2021 Presburger Award
• 2019 Sloan Fellowship

He has advised numerous PhD students including Nathan Klein (now Assistant Professor at Boston University), Kuikui Liu (now Assistant Professor at MIT), and Nima Anari (now Assistant Professor at Stanford). His research has been supported by prestigious grants including the NSF CAREER Award and ONR Young Investigator Award. Oveis Gharan has also been actively involved in the theoretical computer science community through program committee service for major conferences and editorial work for the SIAM Journal of Computing.