| 2025 | FOCS | Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave Sequences. | Jonathan Leake, Kasper Lindberg, Shayan Oveis Gharan |
| 2025 | STOC | On Approximability of the Permanent of PSD Matrices. | Farzam Ebrahimnejad, Ansh Nagda, Shayan Oveis Gharan |
| 2023 | IPCO | A Deterministic Better-than-3/2 Approximation Algorithm for Metric TSP. | Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan |
| 2022 | FOCS | A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP. | Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan |
| 2022 | STOC | An improved approximation algorithm for the minimum | Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan, Xinzhi Zhang |
| 2021 | FOCS | A Matrix Trickle-Down Theorem on Simplicial Complexes and Applications to Sampling Colorings. | Dorna Abdolazimi, Kuikui Liu, Shayan Oveis Gharan |
| 2021 | STOC | Log-concave polynomials IV: approximate exchange, tight mixing times, and near-optimal sampling of forests. | Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant, Thuy-Duong Vuong |
| 2021 | STOC | A (slightly) improved approximation algorithm for metric TSP. | Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan |
| 2020 | FOCS | Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model. | Nima Anari, Kuikui Liu, Shayan Oveis Gharan |
| 2020 | SODA | Composable Core-sets for Determinant Maximization Problems via Spectral Spanners. | Piotr Indyk, Sepideh Mahabadi, Shayan Oveis Gharan, Alireza Rezaei |
| 2020 | STOC | An improved approximation algorithm for TSP in the half integral case. | Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan |
| 2019 | ICML | Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm. | Sepideh Mahabadi, Piotr Indyk, Shayan Oveis Gharan, Alireza Rezaei |
| 2019 | ICML | A Polynomial Time MCMC Method for Sampling from Continuous Determinantal Point Processes. | Alireza Rezaei, Shayan Oveis Gharan |
| 2019 | STOC | Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid. | Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant |
| 2018 | COLT | Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials. | Paul Beame, Shayan Oveis Gharan, Xin Yang |
| 2018 | FOCS | Log-Concave Polynomials, Entropy, and a Deterministic Approximation Algorithm for Counting Bases of Matroids. | Nima Anari, Shayan Oveis Gharan, Cynthia Vinzant |
| 2018 | SODA | Approximating the Largest Root and Applications to Interlacing Families. | Nima Anari, Shayan Oveis Gharan, Amin Saberi, Nikhil Srivastava |
| 2018 | SODA | Nash Social Welfare for Indivisible Items under Separable, Piecewise-Linear Concave Utilities. | Nima Anari, Tung Mai, Shayan Oveis Gharan, Vijay V. Vazirani |
| 2018 | STOC | A simply exponential upper bound on the maximum number of stable matchings. | Anna R. Karlin, Shayan Oveis Gharan, Robbie Weber |
| 2017 | FOCS | Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices. | Nima Anari, Leonid Gurvits, Shayan Oveis Gharan, Amin Saberi |
| 2017 | SODA | Approximation Algorithms for Finding Maximum Induced Expanders. | Shayan Oveis Gharan, Alireza Rezaei |
| 2017 | STOC | A generalization of permanent inequalities and applications in counting and optimization. | Nima Anari, Shayan Oveis Gharan |
| 2016 | COLT | Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes. | Nima Anari, Shayan Oveis Gharan, Alireza Rezaei |
| 2015 | FOCS | Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP. | Nima Anari, Shayan Oveis Gharan |
| 2014 | SODA | Partitioning into Expanders. | Shayan Oveis Gharan, Luca Trevisan |
| 2013 | STOC | Improved Cheeger's inequality: analysis of spectral partitioning algorithms through higher order spectral gap. | Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Shayan Oveis Gharan, Luca Trevisan |
| 2012 | FOCS | Approximating the Expansion Profile and Almost Optimal Local Graph Clustering. | Shayan Oveis Gharan, Luca Trevisan |
| 2012 | ICALP | A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem. | Bundit Laekhanukit, Shayan Oveis Gharan, Mohit Singh |
| 2012 | SODA | Simultaneous approximations for adversarial and stochastic online budgeted allocation. | Vahab S. Mirrokni, Shayan Oveis Gharan, Morteza Zadimoghaddam |
| 2012 | STOC | Multi-way spectral partitioning and higher-order cheeger inequalities. | James R. Lee, Shayan Oveis Gharan, Luca Trevisan |
| 2011 | ESA | On Variants of the Matroid Secretary Problem. | Shayan Oveis Gharan, Jan Vondrk |
| 2011 | FOCS | A Randomized Rounding Approach to the Traveling Salesman Problem. | Shayan Oveis Gharan, Amin Saberi, Mohit Singh |
| 2011 | SODA | The Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus. | Shayan Oveis Gharan, Amin Saberi |
| 2011 | SODA | Submodular Maximization by Simulated Annealing. | Shayan Oveis Gharan, Jan Vondrk |
| 2011 | SODA | Online Stochastic Matching: Online Actions Based on Offline Statistics. | Vahideh H. Manshadi, Shayan Oveis Gharan, Amin Saberi |
| 2010 | SODA | An O(log n/ log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem. | Arash Asadpour, Michel X. Goemans, Aleksander Madry, Shayan Oveis Gharan, Amin Saberi |
| 2007 | SODA | Minimizing movement. | Erik D. Demaine, Mohammad Taghi Hajiaghayi, Hamid Mahini, Amin S. Sayedi-Roshkhar, Shayan Oveis Gharan, Morteza Zadimoghaddam |