17 citations · 97 across the 38 of their papers we have counts for
45 papers
Sampling from the Hardcore Model on Random Regular Bipartite Graphs above the Uniqueness Threshold
Nicholas Kocurek, Shayan Oveis Gharan, Dante Tjowasi
We design an efficient sampling algorithm to generate samples from the hardcore model on random regular bipartite graphs as long as , where is the d…
On Optimization and Counting of Non-Broken Bases of Matroids
Dorna Abdolazimi, Kasper Lindberg, Shayan Oveis Gharan
Given a matroid , and a total ordering over the elements , a broken circuit is a circuit where the smallest element is removed and an NBC independent set is an i…
Complete Log Concavity of Coverage-Like Functions
Dorna Abdolazimi, Shayan Oveis Gharan
We introduce an expressive subclass of non-negative almost submodular set functions, called strongly 2-coverage functions which include coverage and (sums of) matroid rank function…
A (Slightly) Improved Deterministic Approximation Algorithm for Metric TSP
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan
We show that the max entropy algorithm can be derandomized (with respect to a particular objective function) to give a deterministic approximation algorithm for metric TSP…
An Improved Trickle-Down Theorem for Partite Complexes
Dorna Abdolazimi, Shayan Oveis Gharan
We prove a strengthening of the trickle down theorem for partite complexes. Given a -partite -dimensional simplicial complex, we show that if "on average" the links of fa…
Matroid Partition Property and the Secretary Problem
Dorna Abdolazimi, Anna R. Karlin, Nathan Klein +1
A matroid on a set of elements has the -partition property, for some , if it is possible to (randomly) construct a partition matroid on (a s…