  In this paper we relate the partition function to the max-statistics of
random variables. In particular, we provide a novel framework for approximating
and bounding the partition function using MAP inference on randomly perturbed
models. As a result, we can use efficient MAP solvers such as graph-cuts to
evaluate the corresponding partition function. We show that our method excels
in the typical "high signal - high coupling" regime that results in ragged
energy landscapes difficult for alternative approaches.
