N. Anari, S. Oveis Gharan, A. Saberi, N. Srivastava Approximating the Largest Root and Applications to Interlacing Families, SODA 2018.
N. Anari, T. Mai, S. Oveis Gharan, V. Vazirani Nash Social Welfare for Indivisible Items under Separable, Piecewise-Linear Concave Utilities, SODA 2018.
N. Anari, S. Oveis Gharan, A. Saberi, M. Singh Nash Social Welfare, Matrix Permanent, and Stable Polynomials, ITCS, 2017.
N. Anari, S. Oveis Gharan Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP, FOCS 2015.
N. Anari, S. Oveis Gharan The Kadison-Singer Problem for Strongly Rayleigh Measures and Applications to Asymmetric TSP, FOCS 2015.
B. Laekhanukit, S. Oveis Gharan, M. Singh, A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem , ICALP 2012.
S. Oveis Gharan, A. Saberi, M. Singh, A Randomized Rounding Approach to the Traveling Salesman Problem. , FOCS 2011, best paper award.
S. Oveis Gharan, A. Saberi, The Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus , SODA 2011.
S. Oveis Gharan, J. Vondrak, Submodular Maximization by Simulated Annealing, SODA 2011.
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.
E. Demaine, M. Hajiaghayi, H. Mahini, S. Oveis Gharan, M. Zadimoghaddam, Minimizing Movement, SODA 2007, TALG 2009.
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.
S. Oveis Gharan, A. Rezaei, A Polynomial Time MCMC Method for Sampling from Continuous DPPs, 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, 2018.
A. Anari, L. Gurvits, S. Oveis Gharan, A. Saberi Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices, FOCS 2017.
A. Anari, S. Oveis Gharan, A Generalization of Permanent Inequalities and Applications in Counting and Optimization, STOC 2017.
N. Anari, S. Oveis Gharan, A. Rezaei, Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes, COLT 2016.
P. Beame, S. Oveis Gharan, X. Yang, Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions, COLT 2018.
V. Levi Alev, N. Anari, L. C. Lau and S. Oveis Gharan, Graph Clustering using Effective Resistance, ITCS 2018.
R. Lyons, S. Oveis Gharan, Sharp Bounds on Random Walk Eigenvalues via Spectral Embedding IMRN 2017.
S. Oveis Gharan, A. Rezaei, Approximation Algorithms for Finding Maximum Induced Expanders, SODA 2017.
R. Andersen, Y. Peres, S. Oveis Gharan, L. Trevisan, Almost Optimal Local Graph Clustering Using Evolving Sets, JACM 2016.
S. Oveis Gharan, L. Trevisan, Partitioning into Expanders, SODA 2014.
S. Oveis Gharan, L. Trevisan, A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold-Rank Graphs, Approx 2013, invited to Theory of Computing 2015.
S. Oveis Gharan, L. Trevisan, Improved ARV Rounding in Small-set Expanders and Graphs of Bounded Threshold Rank, 2013.
S. Oveis Gharan, L. Trevisan, A Universal upper bound on Graph Diameter based on Laplacian Eigenvalues, 2012.
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.
S. Oveis Gharan, L. Trevisan, Approximating the Expansion Profile and Almost Optimal Local Graph Clustering, FOCS 2012.
J. R. Lee, S. Oveis Gharan, L. Trevisan, Multi-way spectral partitioning and higher-order Cheeger inequalities , STOC 2012, JACM 2014.
M. Akbarpour, S. Li, S. Oveis Gharan, Dynamic Matching Market Design, EC 2014.
V. Mirrokni, S. Oveis Gharan, M. Zadimoghaddam, Simultaneous approximations for adversarial and stochastic online budgeted allocation , SODA 2012.
S. Oveis Gharan, J. Vondrak On Variants of the Matroid Secretary Problem , ESA 2011, invited to Algorithmica 2013.
V. H. Manshadi, S. Oveis Gharan, A. Saberi Online Stochastic Matching: Online Actions Based on Offline Statistics , SODA 2011, MOR 2013.