Shayan Oveis Gharan

Associate Professor
Computer Science and Engineering
University of Washington
A short bio and my CV

I am mainly interested in the design and analysis of algorithms using algebraic techniques.
In Spring 2019 I co-organized a semester long program on Geometry of Polynomials. Here is a research vignette about my works on Log-concave polynomials with connections to the Geometry of Polynomials program.

Recent/Selected Publications

F. Ebrahimnejad, A. Nagda, S. Oveis Gharan Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs, 2021.

A. Karlin, N. Klein, S. Oveis Gharan, X. Zhang An Improved Approximation Algorithm for the Minimum k-Edge Connected Multi-Subgraph Problem, 2021.

N. Anari, K. Liu, S. Oveis Gharan, Cynthia Vinzant, T. Vuong, Log-Concave Polynomials IV: Approximate Exchange, Tight Mixing Times, and Near-Optimal Sampling of Forests, STOC 2021.

A. Karlin, N. Klein, S. Oveis Gharan, A (Slightly) Improved Approximation Algorithm for Metric TSP, STOC 2021.

N. Anari, K. Liu, S. Oveis Gharan, Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model, FOCS 2020, invited to special issue.

N. Anari, K. Liu, S. Oveis Gharan, C. Vinzant, Log-Concave Polynomials III: Mason's Ultra-Log-Concavity Conjecture for Independent Sets of Matroids, submitted, 2018.

N. Anari, K. Liu, S. Oveis Gharan, C. Vinzant, Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid, STOC 2019.

N. Anari, S. Oveis Gharan, C. Vinzant, Log-Concave Polynomials I: Entropy and a Deterministic Approximation Algorithm for Counting Bases of Matroids, FOCS 2018.

N. Anari, S. Oveis Gharan, Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP. See also our recent extension of the proof of Kadison-Singer conjecture by Marcus, Spielman, and Srivastava. See this note for a somewhat short exposition of the ideas. Also, here are short and long presentations of the ideas of the paper. See here for a nice article by Dana Mackenzie about this article.

S. Oveis Gharan, New Rounding Techniques for the Design and Analysis of Approximation Algorithms , PhD thesis, Stanford 2013, ACM Doctoral Dissertation Award Honorable Mention.

S. Oveis Gharan, A. Saberi, M. Singh, A Randomized Rounding Approach to the Traveling Salesman Problem. , FOCS 2011, best paper award.

J. R. Lee, S. Oveis Gharan, L. Trevisan, Multi-way spectral partitioning and higher-order Cheeger inequalities , STOC 2012, JACM 2014.

A. Asadpour, A. Madry, M. Goemans, S. Oveis Gharan, A. Saberi, An O(log n/ log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem , SODA 2010, best paper award.

See here for a full list of my publications.

Awards and Honors:

Program Committee: SODA 2015, APPROX 2016, ESA 2017, ITCS 2018, FOCS 2019, SODA 2021.

Students / Mentee:


Contact Information

Room 636, Paul Allen Center for Computer Science & Engineering
Box 352350,
University of Washington,
Seattle, WA 98195-2350.
(206) 685-2181
email: where my_first_name=shayan