Valency Hub
alphaFeedback
SG

Shayan Oveis Gharan

0000-0002-5504-0849
cs.DSmath.COmath.PRcs.DMcs.CCmath.SPcs.LGstat.MLcs.GTcs.IT

On Valency

published · living versions
W_qr7ewazh·v1 · currentpublished
Local-to-Global Theorems Based on Cones with Applications to Graph Coloring
with Anqi Li
1 version
W_j4q3zw6g·v1published
Rank-1-perturbed trickledown theorems: Mixing time of Glauber dynamics for the Sherrington-Kirkpatrick model up to β≤12+εβ\leq \frac{1}{2}+\varepsilon

Preprints & journals

54 papers in the corpus · 2009–2026
Rank-1-perturbed trickledown theorems: Mixing time of Glauber dynamics for the Sherrington-Kirkpatrick model up to β≤12+ε\beta\leq \frac{1}{2}+\varepsilon2609.13138v1 · Mathews Boban, Anqi Li, Shayan Oveis Gharan2026 · 0 citationsarXivon Valency
On Thin Perfect Matchings up to Polylogarithmic Factors2606.01330v2 · Alireza Haqi, Shayan Oveis Gharan2026 · 0 citationsarXiv
High-Dimensional Expanders, the Sparsest Cut Problem, and Steurer's Conjecture2606.00292v1 · Farzam Ebrahimnejad, Shayan Oveis Gharan2026 · 0 citationsarXiv
Sampling from the Hardcore Model on Random Regular Bipartite Graphs above the Uniqueness Threshold2604.21847v1 · Nicholas Kocurek, Shayan Oveis Gharan, Dante Tjowasi2026 · 0 citationsarXiv
Trickle-down Theorems via C-Lorentzian Polynomials II: Pairwise Spectral Influence and Improved Dobrushin's Condition2510.06549v3 · Jonathan Leake, Shayan Oveis Gharan2025 · 0 citationsarXiv
Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave Sequences2503.01005v3 · Jonathan Leake, Kasper Lindberg, Shayan Oveis Gharan2025 · 1 citationarXiv
Unweighted One-Sided Code Sparsifiers and Thin Subgraphs2502.02799v2 · Shayan Oveis Gharan, Arvin Sahami2025 · 0 citationsarXiv
On approximability of the Permanent of PSD matrices2404.10959v1 · Farzam Ebrahimnejad, Ansh Nagda, Shayan Oveis Gharan2024 · 1 citationarXiv
On Optimization and Counting of Non-Broken Bases of Matroids2305.03307v1 · Dorna Abdolazimi, Kasper Lindberg, Shayan Oveis Gharan2023 · 3 citationsarXiv
Complete Log Concavity of Coverage-Like Functions2303.03741v1 · Dorna Abdolazimi, Shayan Oveis Gharan2023 · 0 citationsarXiv
A (Slightly) Improved Deterministic Approximation Algorithm for Metric TSP2212.06296v1 · Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan2022 · 0 citationsarXiv
Matroid Partition Property and the Secretary Problem2111.12436v1 · Dorna Abdolazimi, Anna R. Karlin, Nathan Klein et al.2021 · 1 citationarXiv
A Matrix Trickle-Down Theorem on Simplicial Complexes and Applications to Sampling Colorings2106.03845v2 · Dorna Abdolazimi, Kuikui Liu, Shayan Oveis Gharan2021 · 5 citationsarXiv
A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP2105.10043v3 · Anna Karlin, Nathan Klein, Shayan Oveis Gharan2021 · 15 citationsarXiv
Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs2103.08683v1 · Farzam Ebrahimnejad, Ansh Nagda, Shayan Oveis Gharan2021 · 0 citationsarXiv
An Improved Approximation Algorithm for the Minimum kk-Edge Connected Multi-Subgraph Problem2101.05921v2 · Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan et al.2021 · 7 citationsarXiv
A (Slightly) Improved Approximation Algorithm for Metric TSP2007.01409v6 · Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan2020 · 128 citationsarXiv
Log-Concave Polynomials IV: Approximate Exchange, Tight Mixing Times, and Near-Optimal Sampling of Forests2004.07220v2 · Nima Anari, Kuikui Liu, Shayan Oveis Gharan et al.2020 · 26 citationsarXiv
Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model2001.00303v3 · Nima Anari, Kuikui Liu, Shayan Oveis Gharan2020 · 100 citationsarXiv
An Improved Approximation Algorithm for TSP in the Half Integral Case1908.00227v1 · Anna Karlin, Nathan Klein, Shayan Oveis Gharan2019 · 23 citationsarXiv
Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm1907.03197v1 · Piotr Indyk, Sepideh Mahabadi, Shayan Oveis Gharan et al.2019 · 2 citationsarXiv
Log-Concave Polynomials III: Mason's Ultra-Log-Concavity Conjecture for Independent Sets of Matroids1811.01600v1 · Nima Anari, Kuikui Liu, Shayan Oveis Gharan et al.2018 · 24 citationsarXiv
Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid1811.01816v3 · Nima Anari, Kuikui Liu, Shayan Oveis Gharan et al.2018 · 104 citationsarXiv
A Polynomial Time MCMC Method for Sampling from Continuous DPPs1810.08867v1 · Shayan Oveis Gharan, Alireza Rezaei2018 · 4 citationsarXiv
Composable Core-sets for Determinant Maximization Problems via Spectral Spanners1807.11648v2 · Piotr Indyk, Sepideh Mahabadi, Shayan Oveis Gharan et al.2018 · 9 citationsarXiv
Log-Concave Polynomials I: Entropy and a Deterministic Approximation Algorithm for Counting Bases of Matroids1807.00929v2 · Nima Anari, Shayan Oveis Gharan, Cynthia Vinzant2018 · 45 citationsarXiv
On the Bias of Reed-Muller Codes over Odd Prime Fields1806.06973v1 · Paul Beame, Shayan Oveis Gharan, Xin Yang2018 · 5 citationsarXiv
Graph Clustering using Effective Resistance1711.06530v1 · Vedat Levi Alev, Nima Anari, Lap Chi Lau et al.2017 · 12 citationsarXiv
A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings1711.01032v2 · Anna R. Karlin, Shayan Oveis Gharan, Robbie Weber2017 · 18 citationsarXiv
Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions1708.02640v1 · Paul Beame, Shayan Oveis Gharan, Xin Yang2017 · 7 citationsarXiv
Approximating the Largest Root and Applications to Interlacing Families1704.03892v1 · Nima Anari, Shayan Oveis Gharan, Amin Saberi et al.2017 · 1 citationarXiv
Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices1704.03486v1 · Nima Anari, Leonid Gurvits, Shayan Oveis Gharan et al.2017 · 21 citationsarXiv
A Generalization of Permanent Inequalities and Applications in Counting and Optimization1702.02937v1 · Nima Anari, Shayan Oveis Gharan2017 · 41 citationsarXiv
Nash Social Welfare for Indivisible Items under Separable, Piecewise-Linear Concave Utilities1612.05191v3 · Nima Anari, Tung Mai, Shayan Oveis Gharan et al.2016 · 65 citationsarXiv
Nash Social Welfare, Matrix Permanent, and Stable Polynomials1609.07056v2 · Nima Anari, Shayan Oveis Gharan, Amin Saberi et al.2016 · 41 citationsarXiv
Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes1602.05242v3 · Nima Anari, Shayan Oveis Gharan, Alireza Rezaei2016 · 25 citationsarXiv
Approximation Algorithms for Finding Maximum Induced Expanders1511.02786v1 · Shayan Oveis Gharan, Alireza Rezaei2015 · 1 citationarXiv
The Kadison-Singer Problem for Strongly Rayleigh Measures and Applications to Asymmetric TSP1412.1143v2 · Nima Anari, Shayan Oveis Gharan2014 · 14 citationsarXiv
Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP1411.4613v4 · Nima Anari, Shayan Oveis Gharan2014 · 38 citationsarXiv
Dynamic Matching Market Design1402.3643v1 · Mohammad Akbarpour, Shengwu Li, Shayan Oveis Gharan2014 · 13 citationsarXiv
Partitioning into Expanders1309.3223v3 · Shayan Oveis Gharan, Luca Trevisan2013 · 0 citationsarXiv
Improved ARV Rounding in Small-set Expanders and Graphs of Bounded Threshold Rank1304.2060v2 · Shayan Oveis Gharan, Luca Trevisan2013 · 3 citationsarXiv
Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap1301.5584v1 · Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee et al.2013 · 23 citationsarXiv
A Universal upper bound on Graph Diameter based on Laplacian Eigenvalues1212.2701v1 · Shayan Oveis Gharan, Luca Trevisan2012 · 1 citationarXiv
A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs1212.1831v1 · Shayan Oveis Gharan, Luca Trevisan2012 · 7 citationsarXiv
Sharp Bounds on Random Walk Eigenvalues via Spectral Embedding1211.0589v3 · Russell Lyons, Shayan Oveis Gharan2012 · 30 citationsIMRN (2017), rnx082
A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem1205.1262v2 · Bundit Laekhanukit, Shayan Oveis Gharan, Mohit Singh2012 · 7 citationsarXiv
Approximating the Expansion Profile and Almost Optimal Local Graph Clustering1204.2021v3 · Shayan Oveis Gharan, Luca Trevisan2012 · 53 citationsarXiv
Multi-way spectral partitioning and higher-order Cheeger inequalities1111.1055v6 · James R. Lee, Shayan Oveis Gharan, Luca Trevisan2011 · 117 citationsarXiv
A Higher-Order Cheeger's Inequality1107.2686v2 · Shayan Oveis Gharan, Luca Trevisan2011 · 3 citationsarXiv
Career total: 105 works. 54 are in this corpus.Showing the 50 most recent.

Profile built from the corpus for this byline.

Author records are still filling in while the Hub is in alpha. If this is your page, you'll be able to claim it soon. Spot a mistake? Tell us.