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 and applied probability.
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, entropy, and a deterministic approximation algorithm for counting bases of matroids, FOCS 2018.
N. Anari, S. Oveis Gharan, A Generalization of Permanent Inequalities and Applications in Counting and Optimization, 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