Minimizing movement. - Erik D. Demaine; Mohammad Taghi Hajiaghayi; Hamid Mahini; Amin S. Sayedi-Roshkhar; Shayan Oveis Gharan; Morteza Zadimoghaddam (SODA, 2007)

Spanning trees with minimum weighted degrees. - Mohammad Ghodsi; Hamid Mahini; Kian Mirjalali; Shayan Oveis Gharan; Amin S. Sayedi-Roshkhar; Morteza Zadimoghaddam (Inf. Process. Lett., 2007)

A Time Warping Speech Recognition System Based on Particle Swarm Optimization. - Saeed Rategh; Farbod Razzazi; Amir Masoud Rahmani; Shayan Oveis Gharan (Asia International Conference on Modelling and Simulation, 2008)

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 (SODA, 2010)

On Variants of the Matroid Secretary Problem. - Shayan Oveis Gharan; Jan Vondrák (ESA, 2011)

A Randomized Rounding Approach to the Traveling Salesman Problem. - Shayan Oveis Gharan; Amin Saberi; Mohit Singh (FOCS, 2011)

The Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus. - Shayan Oveis Gharan; Amin Saberi (SODA, 2011)

Submodular Maximization by Simulated Annealing. - Shayan Oveis Gharan; Jan Vondrák (SODA, 2011)

Online Stochastic Matching: Online Actions Based on Offline Statistics. - Vahideh H. Manshadi; Shayan Oveis Gharan; Amin Saberi (SODA, 2011)

Approximating the Expansion Profile and Almost Optimal Local Graph Clustering. - Shayan Oveis Gharan; Luca Trevisan 001 (FOCS, 2012)

A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem. - Bundit Laekhanukit; Shayan Oveis Gharan; Mohit Singh (ICALP (1), 2012)

Simultaneous approximations for adversarial and stochastic online budgeted allocation. - Vahab S. Mirrokni; Shayan Oveis Gharan; Morteza Zadimoghaddam (SODA, 2012)

Multi-way spectral partitioning and higher-order cheeger inequalities. - James R. Lee; Shayan Oveis Gharan; Luca Trevisan 001 (STOC, 2012)

Sharp Bounds on Random Walk Eigenvalues via Spectral Embedding - Russell Lyons; Shayan Oveis Gharan (CoRR, 2012)

A Universal upper bound on Graph Diameter based on Laplacian Eigenvalues - Shayan Oveis Gharan; Luca Trevisan 001 (CoRR, 2012)

A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs. - Shayan Oveis Gharan; Luca Trevisan 001 (APPROX-RANDOM, 2013)

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 001 (STOC, 2013)

Improved ARV Rounding in Small-set Expanders and Graphs of Bounded Threshold Rank - Shayan Oveis Gharan; Luca Trevisan 001 (CoRR, 2013)

Dynamic matching market design. - Mohammad Akbarpour; Shengwu Li; Shayan Oveis Gharan (EC, 2014)

Partitioning into Expanders. - Shayan Oveis Gharan; Luca Trevisan 001 (SODA, 2014)

Effective-Resistance-Reducing Flows and Asymmetric TSP. - Nima Anari; Shayan Oveis Gharan (CoRR, 2014)

The Kadison-Singer Problem for Strongly Rayleigh Measures and Applications to Asymmetric TSP. - Nima Anari; Shayan Oveis Gharan (CoRR, 2014)

Multiway Spectral Partitioning and Higher-Order Cheeger Inequalities. - James R. Lee; Shayan Oveis Gharan; Luca Trevisan 001 (J. ACM, 2014)

Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP. - Nima Anari; Shayan Oveis Gharan (FOCS, 2015)

Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes. - Nima Anari; Shayan Oveis Gharan; Alireza Rezaei 001 (COLT, 2016)

Monte Carlo Markov Chains Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes. - Nima Anari; Shayan Oveis Gharan; Alireza Rezaei 001 (CoRR, 2016)

Almost Optimal Local Graph Clustering Using Evolving Sets. - Reid Andersen; Shayan Oveis Gharan; Yuval Peres; Luca Trevisan 001 (J. ACM, 2016)

Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices. - Nima Anari; Leonid Gurvits; Shayan Oveis Gharan; Amin Saberi (FOCS, 2017)

Nash Social Welfare, Matrix Permanent, and Stable Polynomials. - Nima Anari; Shayan Oveis Gharan; Amin Saberi; Mohit Singh (ITCS, 2017)

Approximation Algorithms for Finding Maximum Induced Expanders. - Shayan Oveis Gharan; Alireza Rezaei 001 (SODA, 2017)

A generalization of permanent inequalities and applications in counting and optimization. - Nima Anari; Shayan Oveis Gharan (STOC, 2017)

Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions. - Paul Beame; Shayan Oveis Gharan; Xin Yang 017 (Electron. Colloquium Comput. Complex., 2017)

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 (Oper. Res., 2017)

Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials. - Paul Beame; Shayan Oveis Gharan; Xin Yang 017 (COLT, 2018)

Log-Concave Polynomials, Entropy, and a Deterministic Approximation Algorithm for Counting Bases of Matroids. - Nima Anari; Shayan Oveis Gharan; Cynthia Vinzant (FOCS, 2018)

Graph Clustering using Effective Resistance. - Vedat Levi Alev; Nima Anari; Lap Chi Lau; Shayan Oveis Gharan (ITCS, 2018)

Approximating the Largest Root and Applications to Interlacing Families. - Nima Anari; Shayan Oveis Gharan; Amin Saberi; Nikhil Srivastava (SODA, 2018)

Nash Social Welfare for Indivisible Items under Separable, Piecewise-Linear Concave Utilities. - Nima Anari; Tung Mai; Shayan Oveis Gharan; Vijay V. Vazirani (SODA, 2018)

A simply exponential upper bound on the maximum number of stable matchings. - Anna R. Karlin; Shayan Oveis Gharan; Robbie Weber (STOC, 2018)

A Polynomial Time MCMC Method for Sampling from Continuous DPPs. - Shayan Oveis Gharan; Alireza Rezaei 001 (CoRR, 2018)

Log-Concave Polynomials III: Mason's Ultra-Log-Concavity Conjecture for Independent Sets of Matroids. - Nima Anari; Kuikui Liu; Shayan Oveis Gharan; Cynthia Vinzant (CoRR, 2018)

Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm. - Sepideh Mahabadi; Piotr Indyk; Shayan Oveis Gharan; Alireza Rezaei 001 (ICML, 2019)

A Polynomial Time MCMC Method for Sampling from Continuous Determinantal Point Processes. - Alireza Rezaei 001; Shayan Oveis Gharan (ICML, 2019)

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 (STOC, 2019)

Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model. - Nima Anari; Kuikui Liu; Shayan Oveis Gharan (FOCS, 2020)

Composable Core-sets for Determinant Maximization Problems via Spectral Spanners. - Piotr Indyk; Sepideh Mahabadi; Shayan Oveis Gharan; Alireza Rezaei 001 (SODA, 2020)

An improved approximation algorithm for TSP in the half integral case. - Anna R. Karlin; Nathan Klein; Shayan Oveis Gharan (STOC, 2020)

Log-Concave Polynomials IV: Exchange Properties, Tight Mixing Times, and Faster Sampling of Spanning Trees. - Nima Anari; Kuikui Liu; Shayan Oveis Gharan; Cynthia Vinzant (CoRR, 2020)

On the Bias of Reed-Muller Codes over Odd Prime Fields. - Paul Beame; Shayan Oveis Gharan; Xin Yang 017 (SIAM J. Discret. Math., 2020)

A Matrix Trickle-Down Theorem on Simplicial Complexes and Applications to Sampling Colorings. - Dorna Abdolazimi; Kuikui Liu; Shayan Oveis Gharan (FOCS, 2021)

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 (STOC, 2021)

A (slightly) improved approximation algorithm for metric TSP. - Anna R. Karlin; Nathan Klein; Shayan Oveis Gharan (STOC, 2021)

An Improved Approximation Algorithm for the Minimum k-Edge Connected Multi-Subgraph Problem. - Anna R. Karlin; Nathan Klein; Shayan Oveis Gharan; Xinzhi Zhang 002 (CoRR, 2021)

A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP. - Anna R. Karlin; Nathan Klein; Shayan Oveis Gharan (FOCS, 2022)

Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs. - Farzam Ebrahimnejad; Ansh Nagda; Shayan Oveis Gharan (ITCS, 2022)

An improved approximation algorithm for the minimum k-edge connected multi-subgraph problem. - Anna R. Karlin; Nathan Klein; Shayan Oveis Gharan; Xinzhi Zhang 002 (STOC, 2022)

A (Slightly) Improved Deterministic Approximation Algorithm for Metric TSP. - Anna R. Karlin; Nathan Klein; Shayan Oveis Gharan (CoRR, 2022)

On Optimization and Counting of Non-Broken Bases of Matroids. - Dorna Abdolazimi; Kasper Lindberg; Shayan Oveis Gharan (APPROX/RANDOM, 2023)

An Improved Trickle down Theorem for Partite Complexes. - Dorna Abdolazimi; Shayan Oveis Gharan (CCC, 2023)

Matroid Partition Property and the Secretary Problem. - Dorna Abdolazimi; Anna R. Karlin; Nathan Klein; Shayan Oveis Gharan (ITCS, 2023)

A Deterministic Better-than-3/2 Approximation Algorithm for Metric TSP. - Anna R. Karlin; Nathan Klein; Shayan Oveis Gharan (IPCO, 2023)

Complete Log Concavity of Coverage-Like Functions. - Dorna Abdolazimi; Shayan Oveis Gharan (CoRR, 2023)

On Approximability of the Permanent of PSD Matrices. - Farzam Ebrahimnejad; Ansh Nagda; Shayan Oveis Gharan (STOC, 2025)

Unweighted Code Sparsifiers and Thin Subgraphs. - Shayan Oveis Gharan; Arvin Sahami (CoRR, 2025)

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 (CoRR, 2025)

Trickle-down Theorems via C-Lorentzian Polynomials II: Pairwise Spectral Influence and Improved Dobrushin's Condition. - Jonathan Leake; Shayan Oveis Gharan (CoRR, 2025)