6 papers · 1 filter
Linear time approximation of the TV distance between product distributions
Konrad Anand, Alistair Benford, Heng Guo
We present a linear time approximation algorithm of the total variation distance between two product distributions. The main algorithm was found using ChatGPT 5.6 Sol Ultra.
Sink-free orientations: a local sampler with applications
Konrad Anand, Graham Freifeld, Heng Guo +2
For sink-free orientations in graphs of minimum degree at least , we show that there is a deterministic approximate counting algorithm that runs in time $O((n^{73}/\varepsilon^{…
Approximate Counting for Spin Systems in Sub-Quadratic Time
Konrad Anand, Weiming Feng, Graham Freifeld +2
We present two randomised approximate counting algorithms with running time for some constant and accuracy : (1) for the h…
Perfect Sampling for Hard Spheres from Strong Spatial Mixing
Konrad Anand, Andreas Göbel, Marcus Pappik +1
We provide a perfect sampling algorithm for the hard-sphere model on subsets of with expected running time linear in the volume under the assumption of strong spatia…
Perfect Sampling of -Spin Systems on via Weak Spatial Mixing
Konrad Anand, Mark Jerrum
We present a perfect marginal sampler of the unique Gibbs measure of a spin system on . The algorithm is an adaptation of a previous `lazy depth-first' approach by the…
Perfect Sampling in Infinite Spin Systems via Strong Spatial Mixing
Konrad Anand, Mark Jerrum
We present a simple algorithm that perfectly samples configurations from the unique Gibbs measure of a spin system on a potentially infinite graph . The sampling algorithm assum…