A. Karlin, N. Klein, S. Oveis Gharan, A (Slightly) Improved Deterministic Approximation Algorithm for Metric TSP, IPCO, 2023.
A. Karlin, N. Klein, S. Oveis Gharan, A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP, FOCS 2022.
A. Karlin, N. Klein, S. Oveis Gharan, X. Zhang An Improved Approximation Algorithm for the Minimum k-Edge Connected Multi-Subgraph Problem, STOC 2022.
A. Karlin, N. Klein, S. Oveis Gharan, A (Slightly) Improved Approximation Algorithm for Metric TSP, STOC 2021, best paper award.
A. Karlin, N Klein, S. Oveis Gharan, An Improved Approximation Algorithm for TSP in the Half Integral Case, STOC 2020.
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, OR 2018, best paper award.
E. Demaine, M. Hajiaghayi, H. Mahini, S. Oveis Gharan, M. Zadimoghaddam, Minimizing Movement, SODA 2007, TALG 2009.
D. Abdolazimi, K. Lindberg, S. Oveis Gharan, On Optimization and Counting of Non-Broken Bases of Matroids APPROX 2023.
F. Ebrahimnejad, A. Nagda, S. Oveis Gharan Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs, ITCS 2022.
D. Abdolazimi, K. Liu, S. Oveis Gharan A Matrix Trickle-Down Theorem on Simplicial Complexes and Applications to Sampling Colorings, FOCS 2021.
N. Anari, K. Liu, S. Oveis Gharan, Cynthia Vinzant, T. Vuong, Log-Concave Polynomials IV: Approximate Exchange, Tight Mixing Times, and Near-Optimal Sampling of Forests, STOC 2021.
N. Anari, K. Liu, S. Oveis Gharan, Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model, FOCS 2020.
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.
P. Indyk, S. Mahabadi, S. Oveis Gharan, A. Rezaei, Composable Core-sets for Determinant Maximization Problems via Spectral Spanners, SODA 2020.
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, STOC 2019, best paper award, Annals of Math 2023.
N. Anari, S. Oveis Gharan, C. Vinzant Log-concave polynomials I: Entropy, and a Deterministic Approximation Algorithm for Counting Bases of Matroids, FOCS 2018, Duke Math Journal 2021.
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, Advances in Mathematics 2021.
N. Anari, S. Oveis Gharan, A. Rezaei, Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes, COLT 2016.
D. Abdolazimi, K. Lindberg, S. Oveis Gharan, On Optimization and Counting of Non-Broken Bases of Matroids, submitted, 2023.
A. Abdolazimi, S. Oveis Gharan, An Improved Trickle-Down Theorem for Partite Complexes, CCC 2023.
P. Beame, S. Oveis Gharan, X. Yang, Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions, COLT 2018.
A. Abdolazimi, S. Oveis Gharan, An Improved Trickle-Down Theorem for Partite Complexes, CCC 2023.
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.
D. Abdolazimi, A. Karlin, N. Klein, S. Oveis Gharan, Matroid Partition Property and the Secretary Problem, ITCS 2023.
S. Oveis Gharan, A. Rezaei, A Polynomial Time MCMC Method for Sampling from Continuous DPPs, ICML 2019.
P. Indyk, S. Mahabadi, S. Oveis Gharan, A. Rezaei, Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm, ICML 2019.
M. Akbarpour, S. Li, S. Oveis Gharan, Dynamic Matching Market Design, EC 2014, Journal of Political Economy (JPE 2019).
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.