Shayan Oveis Gharan

109 papers A* 35A 7B 1Journal 63Unranked 3

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