17 citations · 97 across the 38 of their papers we have counts for
Showing 2020Show all
3 papers · 1 filter
cs.DS2020★ 1 cited
A (Slightly) Improved Approximation Algorithm for Metric TSP
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan
For some we give a randomized approximation algorithm for metric TSP.
cs.DS2020
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…
cs.DS2020★ 1 cited
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…