9 papers
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.
Simulating Gaussian boson sampling on graphs in polynomial time
Konrad Anand, Zongchen Chen, Mary Cryan +4
We show that a distribution related to Gaussian Boson Sampling (GBS) on graphs can be sampled classically in polynomial time. Graphical applications of GBS typically sample from th…
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^{…
Rapid mixing of the flip chain over non-crossing spanning trees
Konrad Anand, Weiming Feng, Graham Freifeld +3
We show that the flip chain for non-crossing spanning trees of points in convex position mixes in time . We use connections between Fuss-Catalan structures to c…
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…
Probabilistic Analysis of RRT Trees
Konrad Anand, Luc Devroye
This thesis presents analysis of the properties and run-time of the Rapidly-exploring Random Tree (RRT) algorithm. It is shown that the time for the RRT with stepsize to grow c…