Shayan Oveis Gharan

Publication Activity (10 Years)

Years Active: 2007-2023
Publications (10 Years): 65

Top Venues

CoRR

STOC

FOCS

SODA

Publications

Dorna Abdolazimi, Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan
Matroid Partition Property and the Secretary Problem. ITCS (2023)
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan
A Deterministic Better-than-3/2 Approximation Algorithm for Metric TSP. IPCO (2023)
Dorna Abdolazimi, Shayan Oveis Gharan
Complete Log Concavity of Coverage-Like Functions. CoRR (2023)
Dorna Abdolazimi, Shayan Oveis Gharan
An Improved Trickle down Theorem for Partite Complexes. CCC (2023)
Dorna Abdolazimi, Kasper Lindberg, Shayan Oveis Gharan
On Optimization and Counting of Non-Broken Bases of Matroids. CoRR (2023)
Dorna Abdolazimi, Kasper Lindberg, Shayan Oveis Gharan
On Optimization and Counting of Non-Broken Bases of Matroids. APPROX/RANDOM (2023)
Farzam Ebrahimnejad, Ansh Nagda, Shayan Oveis Gharan
Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs. ITCS (2022)
Dorna Abdolazimi, Shayan Oveis Gharan
An Improved Trickle-Down Theorem for Partite Complexes. CoRR (2022)
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan, Xinzhi Zhang
-edge connected multi-subgraph problem. STOC (2022)
Dorna Abdolazimi, Kuikui Liu, Shayan Oveis Gharan
A Matrix Trickle-Down Theorem on Simplicial Complexes and Applications to Sampling Colorings. FOCS (2022)
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan
A (Slightly) Improved Deterministic Approximation Algorithm for Metric TSP. CoRR (2022)
Anna Karlin, Nathan Klein, Shayan Oveis Gharan
A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP. FOCS (2022)
Dorna Abdolazimi, Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan
Matroid Partition Property and the Secretary Problem. CoRR (2021)
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan, Xinzhi Zhang
An Improved Approximation Algorithm for the Minimum k-Edge Connected Multi-Subgraph Problem. CoRR (2021)
Anna Karlin, Nathan Klein, Shayan Oveis Gharan
A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP. CoRR (2021)
Farzam Ebrahimnejad, Ansh Nagda, Shayan Oveis Gharan
Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs. CoRR (2021)
Dorna Abdolazimi, Kuikui Liu, Shayan Oveis Gharan
A Matrix Trickle-Down Theorem on Simplicial Complexes and Applications to Sampling Colorings. FOCS (2021)
Dorna Abdolazimi, Kuikui Liu, Shayan Oveis Gharan
A Matrix Trickle-Down Theorem on Simplicial Complexes and Applications to Sampling Colorings. CoRR (2021)
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan
A (slightly) improved approximation algorithm for metric TSP. STOC (2021)
Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant, Thuy-Duong Vuong
Log-concave polynomials IV: approximate exchange, tight mixing times, and near-optimal sampling of forests. STOC (2021)
Nima Anari, Kuikui Liu, Shayan Oveis Gharan
Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model. FOCS (2020)
Nima Anari, Kuikui Liu, Shayan Oveis Gharan
Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model. CoRR (2020)
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan
An improved approximation algorithm for TSP in the half integral case. STOC (2020)
Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant
Log-Concave Polynomials IV: Exchange Properties, Tight Mixing Times, and Faster Sampling of Spanning Trees. CoRR (2020)
Paul Beame, Shayan Oveis Gharan, Xin Yang
On the Bias of Reed-Muller Codes over Odd Prime Fields. SIAM J. Discret. Math. 34 (2) (2020)
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan
A (Slightly) Improved Approximation Algorithm for Metric TSP. CoRR (2020)
Piotr Indyk, Sepideh Mahabadi, Shayan Oveis Gharan, Alireza Rezaei
Composable Core-sets for Determinant Maximization Problems via Spectral Spanners. SODA (2020)
Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant
Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid. STOC (2019)
Piotr Indyk, Sepideh Mahabadi, Shayan Oveis Gharan, Alireza Rezaei
Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm. CoRR (2019)
Anna Karlin, Nathan Klein, Shayan Oveis Gharan
An Improved Approximation Algorithm for TSP in the Half Integral Case. CoRR (2019)
Alireza Rezaei, Shayan Oveis Gharan
A Polynomial Time MCMC Method for Sampling from Continuous Determinantal Point Processes. ICML (2019)
Sepideh Mahabadi, Piotr Indyk, Shayan Oveis Gharan, Alireza Rezaei
Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm. ICML (2019)
Nima Anari, Shayan Oveis Gharan, Cynthia Vinzant
Log-concave polynomials, entropy, and a deterministic approximation algorithm for counting bases of matroids. CoRR (2018)
Nima Anari, Shayan Oveis Gharan, Amin Saberi, Nikhil Srivastava
Approximating the Largest Root and Applications to Interlacing Families. SODA (2018)
Piotr Indyk, Sepideh Mahabadi, Shayan Oveis Gharan, Alireza Rezaei
Composable Core-sets for Determinant Maximization Problems via Spectral Spanners. CoRR (2018)
Anna R. Karlin, Shayan Oveis Gharan, Robbie Weber
A simply exponential upper bound on the maximum number of stable matchings. STOC (2018)
Shayan Oveis Gharan, Alireza Rezaei
A Polynomial Time MCMC Method for Sampling from Continuous DPPs. CoRR (2018)
Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant
Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid. CoRR (2018)
Nima Anari, Tung Mai, Shayan Oveis Gharan, Vijay V. Vazirani
Nash Social Welfare for Indivisible Items under Separable, Piecewise-Linear Concave Utilities. SODA (2018)
Paul Beame, Shayan Oveis Gharan, Xin Yang
On the Bias of Reed-Muller Codes over Odd Prime Fields. CoRR (2018)
Paul Beame, Shayan Oveis Gharan, Xin Yang
Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials. Electron. Colloquium Comput. Complex. 25 (2018)
Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant
Log-Concave Polynomials III: Mason's Ultra-Log-Concavity Conjecture for Independent Sets of Matroids. CoRR (2018)
Paul Beame, Shayan Oveis Gharan, Xin Yang
Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials. COLT (2018)
Nima Anari, Shayan Oveis Gharan, Cynthia Vinzant
Log-Concave Polynomials, Entropy, and a Deterministic Approximation Algorithm for Counting Bases of Matroids. FOCS (2018)
Vedat Levi Alev, Nima Anari, Lap Chi Lau, Shayan Oveis Gharan
Graph Clustering using Effective Resistance. ITCS (2018)
Nima Anari, Leonid Gurvits, Shayan Oveis Gharan, Amin Saberi
Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices. CoRR (2017)
Nima Anari, Shayan Oveis Gharan
A Generalization of Permanent Inequalities and Applications in Counting and Optimization. CoRR (2017)
Nima Anari, Shayan Oveis Gharan
A generalization of permanent inequalities and applications in counting and optimization. STOC (2017)
Paul Beame, Shayan Oveis Gharan, Xin Yang
Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions. CoRR (2017)
Anna R. Karlin, Shayan Oveis Gharan, Robbie Weber
A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings. CoRR (2017)
Arash Asadpour, Michel X. Goemans, Aleksander Madry, Shayan Oveis Gharan, Amin Saberi
)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem. Oper. Res. 65 (4) (2017)
Nima Anari, Leonid Gurvits, Shayan Oveis Gharan, Amin Saberi
Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices. FOCS (2017)
Vedat Levi Alev, Nima Anari, Lap Chi Lau, Shayan Oveis Gharan
Graph Clustering using Effective Resistance. CoRR (2017)
Nima Anari, Shayan Oveis Gharan, Amin Saberi, Mohit Singh
Nash Social Welfare, Matrix Permanent, and Stable Polynomials. ITCS (2017)
Nima Anari, Shayan Oveis Gharan, Amin Saberi, Nikhil Srivastava
Approximating the Largest Root and Applications to Interlacing Families. CoRR (2017)
Shayan Oveis Gharan, Alireza Rezaei
Approximation Algorithms for Finding Maximum Induced Expanders. SODA (2017)
Paul Beame, Shayan Oveis Gharan, Xin Yang
Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions. Electron. Colloquium Comput. Complex. 24 (2017)
Reid Andersen, Shayan Oveis Gharan, Yuval Peres, Luca Trevisan
Almost Optimal Local Graph Clustering Using Evolving Sets. J. ACM 63 (2) (2016)
Nima Anari, Shayan Oveis Gharan, Alireza Rezaei
Monte Carlo Markov Chains Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes. CoRR (2016)
Nima Anari, Shayan Oveis Gharan, Amin Saberi, Mohit Singh
Nash Social Welfare, Matrix Permanent, and Stable Polynomials. CoRR (2016)
Nima Anari, Shayan Oveis Gharan, Alireza Rezaei
Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes. COLT (2016)
Nima Anari, Tung Mai, Shayan Oveis Gharan, Vijay V. Vazirani
Nash Social Welfare for Indivisible Items under Separable, Piecewise-Linear Concave Utilities. CoRR (2016)
Shayan Oveis Gharan, Luca Trevisan
A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs. Theory Comput. 11 (2015)
Shayan Oveis Gharan, Alireza Rezaei
Approximation Algorithms for Finding Maximum Induced Expanders. CoRR (2015)
Nima Anari, Shayan Oveis Gharan
Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP. FOCS (2015)
Mohammad Akbarpour, Shengwu Li, Shayan Oveis Gharan
Dynamic Matching Market Design. CoRR (2014)
Nima Anari, Shayan Oveis Gharan
The Kadison-Singer Problem for Strongly Rayleigh Measures and Applications to Asymmetric TSP. CoRR (2014)
James R. Lee, Shayan Oveis Gharan, Luca Trevisan
Multiway Spectral Partitioning and Higher-Order Cheeger Inequalities. J. ACM 61 (6) (2014)
Nima Anari, Shayan Oveis Gharan
Effective-Resistance-Reducing Flows and Asymmetric TSP. CoRR (2014)
Mohammad Akbarpour, Shengwu Li, Shayan Oveis Gharan
Dynamic matching market design. EC (2014)
Shayan Oveis Gharan, Luca Trevisan
Partitioning into Expanders. SODA (2014)
Shayan Oveis Gharan, Luca Trevisan
A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs. APPROX-RANDOM (2013)
Shayan Oveis Gharan, Jan Vondrák
On Variants of the Matroid Secretary Problem. Algorithmica 67 (4) (2013)
Shayan Oveis Gharan, Luca Trevisan
Improved ARV Rounding in Small-set Expanders and Graphs of Bounded Threshold Rank CoRR (2013)
Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Shayan Oveis Gharan, Luca Trevisan
Improved Cheeger's inequality: analysis of spectral partitioning algorithms through higher order spectral gap. STOC (2013)
Shayan Oveis Gharan, Luca Trevisan
Partitioning into Expanders. CoRR (2013)
Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Shayan Oveis Gharan, Luca Trevisan
Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap CoRR (2013)
Shayan Oveis Gharan, Luca Trevisan
A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs CoRR (2012)
James R. Lee, Shayan Oveis Gharan, Luca Trevisan
Multi-way spectral partitioning and higher-order cheeger inequalities. STOC (2012)
Bundit Laekhanukit, Shayan Oveis Gharan, Mohit Singh
A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem CoRR (2012)
Shayan Oveis Gharan, Luca Trevisan
Approximating the Expansion Profile and Almost Optimal Local Graph Clustering. FOCS (2012)
Vahab S. Mirrokni, Shayan Oveis Gharan, Morteza Zadimoghaddam
Simultaneous approximations for adversarial and stochastic online budgeted allocation. SODA (2012)
Vahideh H. Manshadi, Shayan Oveis Gharan, Amin Saberi
Online Stochastic Matching: Online Actions Based on Offline Statistics. Math. Oper. Res. 37 (4) (2012)
Shayan Oveis Gharan, Luca Trevisan
A Universal upper bound on Graph Diameter based on Laplacian Eigenvalues CoRR (2012)
Shayan Oveis Gharan, Luca Trevisan
Approximating the Expansion Profile and Almost Optimal Local Graph Clustering CoRR (2012)
Bundit Laekhanukit, Shayan Oveis Gharan, Mohit Singh
A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem. ICALP (1) (2012)
Russell Lyons, Shayan Oveis Gharan
Sharp Bounds on Random Walk Eigenvalues via Spectral Embedding CoRR (2012)
James R. Lee, Shayan Oveis Gharan, Luca Trevisan
Multi-way spectral partitioning and higher-order Cheeger inequalities CoRR (2011)
Vahideh H. Manshadi, Shayan Oveis Gharan, Amin Saberi
Online Stochastic Matching: Online Actions Based on Offline Statistics. SODA (2011)
Shayan Oveis Gharan, Jan Vondrák
Submodular Maximization by Simulated Annealing. SODA (2011)
Shayan Oveis Gharan, Jan Vondrák
On Variants of the Matroid Secretary Problem CoRR (2011)
Shayan Oveis Gharan, Amin Saberi, Mohit Singh
A Randomized Rounding Approach to the Traveling Salesman Problem. FOCS (2011)
Shayan Oveis Gharan, Jan Vondrák
On Variants of the Matroid Secretary Problem. ESA (2011)
Shayan Oveis Gharan, Amin Saberi
The Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus. SODA (2011)
Vahideh H. Manshadi, Shayan Oveis Gharan, Amin Saberi
Online Stochastic Matching: Online Actions Based on Offline Statistics CoRR (2010)
Arash Asadpour, Michel X. Goemans, Aleksander Madry, Shayan Oveis Gharan, Amin Saberi
An O(log n/ log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem. SODA (2010)
Shayan Oveis Gharan, Jan Vondrák
Submodular Maximization by Simulated Annealing CoRR (2010)
Erik D. Demaine, Mohammad Taghi Hajiaghayi, Hamid Mahini, Amin S. Sayedi-Roshkhar, Shayan Oveis Gharan, Morteza Zadimoghaddam
Minimizing movement. ACM Trans. Algorithms 5 (3) (2009)
Shayan Oveis Gharan, Amin Saberi
Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus CoRR (2009)
Saeed Rategh, Farbod Razzazi, Amir Masoud Rahmani, Shayan Oveis Gharan
A Time Warping Speech Recognition System Based on Particle Swarm Optimization. Asia International Conference on Modelling and Simulation (2008)

Shayan Oveis Gharan.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Shayan Oveis Gharan