17 citations · 31 across the 9 of their papers we have counts for
13 papers · 1 filter
Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs
Farzam Ebrahimnejad, Ansh Nagda, Shayan Oveis Gharan
We show that the ratio of the number of near perfect matchings to the number of perfect matchings in -regular strong expander (non-bipartite) graphs, with vertices, is a po…
Log-Concave Polynomials IV: Approximate Exchange, Tight Mixing Times, and Near-Optimal Sampling of Forests
Nima Anari, Kuikui Liu, Shayan Oveis Gharan +2
We prove tight mixing time bounds for natural random walks on bases of matroids, determinantal distributions, and more generally distributions associated with log-concave polynomia…
Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
Nima Anari, Kuikui Liu, Shayan Oveis Gharan
We say a probability distribution is spectrally independent if an associated correlation matrix has a bounded largest eigenvalue for the distribution and all of its conditional…
An Improved Approximation Algorithm for TSP in the Half Integral Case
Anna Karlin, Nathan Klein, Shayan Oveis Gharan
We design a -approximation algorithm for the metric traveling salesperson problem (TSP) for instances in which an optimal solution to the subtour linear programming relaxa…
Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm
Piotr Indyk, Sepideh Mahabadi, Shayan Oveis Gharan +1
``Composable core-sets'' are an efficient framework for solving optimization problems in massive data models. In this work, we consider efficient construction of composable core-se…
Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid
Nima Anari, Kuikui Liu, Shayan Oveis Gharan +1
We design an FPRAS to count the number of bases of any matroid given by an independent set oracle, and to estimate the partition function of the random cluster model of any matroid…