Shayan Oveis Gharan

 
 

contact information


Email:



Phone:


Office Address:

Management Science and Eng.

Huang Engineering Center 314K

475 Via Ortega

Stanford, CA 94305






 

Since October 2008, I am a PhD student of the Information Science and Technology group of the Management Science and Engineering department at Stanford University. I am thrilled to have Amin Saberi as my advisor.

I received my BS in Computer Engineering Department at Sharif University of Technology.

I am a recipient of a Stanford Graduate Fellowship, and a Miller Fellowship.

I will be graduating in June 2013. You can find my Resume here.

Last, but not least, I was born in Esfahan, Iran (Map).

My Research Interests

  1. • Approximation Algorithms, Randomized Algorithms

  2. • Spectral Algorithms, Spectral Graph Theory

  3. • Online Algorithm, Stochastic Optimization, Applied Probability

Selected Publications

Approximation Algorithms

  1. • B. Laekhunakit, S. Oveis Gharan, M. Singh, A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem, ICALP 2012.

  2. • S. Oveis Gharan, A. Saberi, M. Singh, A Randomized Rounding Approach to the Traveling Salesman Problem, FOCS 2011. Awarded Best Paper. A Simons Foundation and Wired article by Erica Klarreich.

  3. • S. Oveis Gharan, A. Saberi, Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus, SODA 2011.

  4. • S. Oveis Gharan, J. Vondrak, Submodular Maximization by Simulated Annealing, SODA 2011.

  5. • A. Asadpour, M. Goemans, A. Madry, S. Oveis Gharan, A. Saberi, An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem, SODA 2010. Awarded Best Paper.

  6. • E. Demaine, M. Hajiaghayi, H. Mahini, A. Sayedi, S. Oveis Gharan, M. Zadimoghaddam, Minimizing Movements, TALG 2009, Conference version appeared in SODA 2007

Spectral Algorithms / Spectral Graph Theory

  1. • S. Oveis Gharan, L. Trevisan, Improved ARV Rounding in Small-set Expanders and Graphs of Bounded Threshold Rank, submitted, 2013.

  2. • T. C. Kwok, L. C. Lau, Y. T. Lee, S. Oveis Gharan, L. Trevisan, Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap, STOC, 2013.

  3. • S. Oveis Gharan, L. Trevisan, A Universal upper bound on Graph Diameter based on Laplacian Eigenvalues, manuscript, 2012.

  4. • S. Oveis Gharan, L. Trevisan, A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs, submitted, 2012.

  5. • R. Lyons, S. Oveis Gharan, Sharp Bounds on Random Walk Eigenvalues via Spectral Embedding, submitted, 2012.

  6. • S. Oveis Gharan, L. Trevisan, Approximating the Expansion Profile and Almost Optimal Local Graph Clustering, FOCS 2012.

  7. • J. R. Lee, S. Oveis Gharan, L. Trevisan, Multi-way Spectral Partitioning and Higher-Order Cheeger Inequalities, STOC 2012.

Stochastic Optimization / Online Algorithms

  1. • V. Mirrokni, S. Oveis Gharan, M. Zadimoghaddam, Simultaneous Approximations for Adversarial and Stochastic Online Budgeted Allocation, SODA 2012.

  2. • S. Oveis Gharan, J. Vondrak, On Variants of the Matroid Secretary Problem, ESA 2011, invited to a special issue of Algorithmica dedicated to ESA 2011.

  3. • V. Manshadi, S. Oveis Gharan, A. Saberi, Online Stochastic Matching: Online Actions Based on Offline Statistics, MOR 2012, Conference version appeared in SODA 2011.