S. Gharan

Most-cited papers

Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid
Nima Anari, Kuikui Liu, S. Gharan, C. Vinzant
2018Symposium on the Theory of Computing244 citations Open access
Semantic Scholar
A (slightly) improved approximation algorithm for metric TSP
Anna R. Karlin, N. Klein, S. Gharan
2020Symposium on the Theory of Computing198 citations
Semantic Scholar
Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
Nima Anari, Kuikui Liu, S. Gharan
2020IEEE Annual Symposium on Foundations of Computer Science196 citations Open access
Semantic Scholar
Thickness and Information in Dynamic Matching Markets
M. Akbarpour, Sheng-Wu Li, S. Gharan
2020Journal of Political Economy163 citations Open access
Semantic Scholar
Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes
Nima Anari, S. Gharan, A. Rezaei
2016Annual Conference Computational Learning Theory140 citations
Semantic Scholar
Log-concave polynomials, I: Entropy and a deterministic approximation algorithm for counting bases of matroids
Nima Anari, S. Gharan, C. Vinzant
2018Duke mathematical journal124 citations Open access
Semantic Scholar
Nash Social Welfare for Indivisible Items under Separable, Piecewise-Linear Concave Utilities
Nima Anari, Tung Mai, S. Gharan, V. Vazirani
2016ACM-SIAM Symposium on Discrete Algorithms82 citations Open access
Semantic Scholar
Nash Social Welfare, Matrix Permanent, and Stable Polynomials
Nima Anari, S. Gharan, A. Saberi, Mohit Singh
2016Information Technology Convergence and Services76 citations
Semantic Scholar
A generalization of permanent inequalities and applications in counting and optimization
Nima Anari, S. Gharan
2017Symposium on the Theory of Computing75 citations
Semantic Scholar
Log-Concave Polynomials III: Mason's Ultra-Log-Concavity Conjecture for Independent Sets of Matroids
Nima Anari, Kuikui Liu, S. Gharan, C. Vinzant
2018Proceedings of the American Mathematical Society69 citations Open access
Semantic Scholar
Graph Clustering using Effective Resistance
Vedat Levi Alev, Nima Anari, L. Lau, S. Gharan
2018Information Technology Convergence and Services59 citations
Semantic Scholar
Log-concave polynomials IV: approximate exchange, tight mixing times, and near-optimal sampling of forests
Nima Anari, Kuikui Liu, S. Gharan, C. Vinzant +1 more
2021Symposium on the Theory of Computing45 citations Open access
Semantic Scholar
A Deterministic Better-than-3/2 Approximation Algorithm for Metric TSP
A. Karlin, N. Klein, S. Gharan
2023Conference on Integer Programming and Combinatorial Optimization32 citations
Semantic Scholar
A simply exponential upper bound on the maximum number of stable matchings
Anna R. Karlin, S. Gharan, Robbie Weber
2017Symposium on the Theory of Computing32 citations Open access
Semantic Scholar
Almost Optimal Local Graph Clustering Using Evolving Sets
Reid Andersen, S. Gharan, Y. Peres, L. Trevisan
2016Journal of the ACM31 citations
Semantic Scholar
A Matrix Trickle-Down Theorem on Simplicial Complexes and Applications to Sampling Colorings
Dorna Abdolazimi, Kuikui Liu, S. Gharan
2021IEEE Annual Symposium on Foundations of Computer Science27 citations Open access
Semantic Scholar
An improved approximation algorithm for TSP in the half integral case
Anna R. Karlin, N. Klein, S. Gharan
2019Symposium on the Theory of Computing26 citations Open access
Semantic Scholar
Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices
Nima Anari, L. Gurvits, S. Gharan, A. Saberi
2017IEEE Annual Symposium on Foundations of Computer Science26 citations Open access
Semantic Scholar
Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm
P. Indyk, S. Mahabadi, S. Gharan, A. Rezaei
2019International Conference on Machine Learning25 citations
Semantic Scholar
A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP
A. Karlin, N. Klein, S. Gharan
2021IEEE Annual Symposium on Foundations of Computer Science24 citations Open access
Semantic Scholar
Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials
P. Beame, S. Gharan, Xin Yang
2018Electron. Colloquium Comput. Complex.24 citations
Semantic Scholar
Composable Core-sets for Determinant Maximization Problems via Spectral Spanners
P. Indyk, S. Mahabadi, S. Gharan, A. Rezaei
2018ACM-SIAM Symposium on Discrete Algorithms23 citations Open access
Semantic Scholar
Matroid Partition Property and the Secretary Problem
Dorna Abdolazimi, Anna R. Karlin, N. Klein, S. Gharan
2021Information Technology Convergence and Services15 citations
Semantic Scholar
Log-Concave Polynomials IV: Exchange Properties, Tight Mixing Times, and Faster Sampling of Spanning Trees
Nima Anari, Kuikui Liu, S. Gharan, C. Vinzant
2020arXiv.org14 citations
Semantic Scholar
A Polynomial Time MCMC Method for Sampling from Continuous Determinantal Point Processes
A. Rezaei, S. Gharan
2019International Conference on Machine Learning14 citations
Semantic Scholar
On the Bias of Reed-Muller Codes over Odd Prime Fields
P. Beame, S. Gharan, Xin Yang
2018SIAM Journal on Discrete Mathematics13 citations Open access
Semantic Scholar
Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions
P. Beame, S. Gharan, Xin Yang
2017Electron. Colloquium Comput. Complex.13 citations
Semantic Scholar
Approximating the Largest Root and Applications to Interlacing Families
Nima Anari, S. Gharan, A. Saberi, N. Srivastava
2017ACM-SIAM Symposium on Discrete Algorithms13 citations Open access
Semantic Scholar
An improved approximation algorithm for the minimum k-edge connected multi-subgraph problem
Anna R. Karlin, N. Klein, S. Gharan, Xinzhi Zhang
2021Symposium on the Theory of Computing12 citations Open access
Semantic Scholar
An Improved Trickle-Down Theorem for Partite Complexes
Dorna Abdolazimi, S. Gharan
2022Cybersecurity and Cyberforensics Conference7 citations Open access
Semantic Scholar
A (Slightly) Improved Deterministic Approximation Algorithm for Metric TSP
A. Karlin, N. Klein, S. Gharan
2022arXiv.org4 citations Open access
Semantic Scholar
A Polynomial Time MCMC Method for Sampling from Continuous DPPs
S. Gharan, A. Rezaei
2018arXiv.org4 citations
Semantic Scholar
Sampling from the Hardcore Model on Random Regular Bipartite Graphs above the Uniqueness Threshold
Nicholas Kocurek, S. Gharan, Dante Tjowasi
2026arXiv.org3 citations
Semantic Scholar
Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs
Farzam Ebrahimnejad, Ansh Nagda, S. Gharan
2021Information Technology Convergence and Services2 citations
Semantic Scholar
On Optimization and Counting of Non-Broken Bases of Matroids
Dorna Abdolazimi, Kasper Lindberg, S. Gharan
2023International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques1 citations Open access
Semantic Scholar
Thickness and Information in Dynamic Matching Markets
M. Akbarpour, Sheng-Wu Li, S. Gharan
20201 citations Open access
Semantic Scholar
The Polynomial Paradigm in Algorithm Design Winter 2020 Lecture 5 : Maximum Entropy Convex Programs
S. Gharan, Jan 27th
20201 citations
Semantic Scholar
Counting and Sampling Fall 2017 Lecture 6 : Graph Coloring Using Path Coupling
S. Gharan
20171 citations
Semantic Scholar
Recent Advances in Approximation Algorithms Spring 2015 Lecture 15 & 16 : Proof of Kadison-Singer Conjecture and the Extensions
S. Gharan
20151 citations
Semantic Scholar
Recent Advances in Approximation Algorithms Spring 2015 Lecture 17 : Cheeger ’ s Inequality and the Sparsest Cut Problem
S. Gharan
20151 citations
Semantic Scholar
Lecture 3: DNF Counting and Unreliability
S. Gharan
20230 citations
Semantic Scholar
Lecture 6: Algorithmic Lov´asz Local Lemma
S. Gharan
20230 citations
Semantic Scholar
Complete Log Concavity of Coverage-Like Functions
Dorna Abdolazimi, S. Gharan
2023arXiv.org0 citations Open access
Semantic Scholar
Randomized Algorithms Spring 2023 Lecture 7 : Negative Correlation and Applications
S. Gharan
20230 citations
Semantic Scholar
Randomized Algorithms Spring 2023 Lecture 8 : Strongly Rayleigh Distributions
S. Gharan
20230 citations
Semantic Scholar
Design Analysis I Lecture 6: Streaming / Locally Sensitive Hashing
S. Gharan
20220 citations
Semantic Scholar
Lecture 11 : Approximate Sampling and High Dimensional Complexes
S. Gharan
20220 citations
Semantic Scholar
Moden Spectral Graph Theory Winter 2022 Lecture 3 : Small Set Expansion Problem
S. Gharan
20220 citations
Semantic Scholar
Schwartz-Zippel Lemma, Perfect Matching
S. Gharan
20220 citations
Semantic Scholar
Lecture 14: Cheeger’s Inequality cont., Spectral Clustering
S. Gharan
20210 citations
Semantic Scholar