Perfect sampling from rapidly mixing Markov chains

Andreas Göbel, Jingcheng Liu, Pasin Manurangsi +1

We show that efficient approximate sampling algorithms, combined with a slow exponential time oracle for computing its output distribution, can be combined into constructing effici…