Shayan Oveis GharanAssistant 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.
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, Submitted, 2018.
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
Current students: Alireza Rezaei, Robbie Weber