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 and applied probability.

Selected Publications

A. 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.

M. Akbarpour, S. Li, S. Oveis Gharan, Dynamic Matching Market Design, preliminary version accepted in EC 2014.

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.

Current students: Alireza Rezaei


Teaching


Contact Information

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