Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting

Daniel Stefankovic, Santosh Vempala, Eric Vigoda

We present a near-optimal reduction from approximately counting the cardinality of a discrete set to approximately sampling elements of the set. An important application of our wor…