Shayan Oveis Gharan

Assistant 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.
If you are interestd in a postdoc position in our group, please see this page

Selected Publications

N. Anari, K. Liu, S. Oveis Gharan, C. Vinzant, Log-Concave Polynomials III: Mason's Ultra-Log-Concavity Conjecture for Independent Sets of Matroids, 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.

P. Indyk, S. Mahabadi, S. Oveis Gharan, A. Rezaei, Composable Core-sets for Determinant Maximization Problems via Spectral Spanners, Submitted, 2018.

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

A. Karlin, S. Oveis Gharan, R. Weber, A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings, STOC 2017.

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.

Current students: Alireza Rezaei, Robbie Weber, Farzam Ebrahimnejad, Kuikui Liu


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