12 papers
On the self-intersection time of non-backtracking random walks
Ferenc Bencs, Leslie Ann Goldberg, Matthew Jenssen +4
We study the self-intersection time of the non-backtracking random walk on connected undirected graphs. For every fixed we show that the expected self-intersection time i…
Fast Mixing for Low-Temperature Potts Models via Poisson Trees
Zongchen Chen, Andreas Galanis, Leslie Ann Goldberg +3
The -state ferromagnetic Potts model on a graph is a probability distribution on all -colourings of that favours many monochromatic edges. Approximate sampling from t…
The Instability of all Backoff Protocols
Leslie Ann Goldberg, John Lapinskas
In this paper we prove Aldous's conjecture from 1987 that there is no backoff protocol that is stable for any positive arrival rate. The setting is a communication channel for coor…
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…
Logarithmic Mixing of Random Walks on Dynamical Random Cluster Models
Andreas Galanis, Leslie Ann Goldberg, Xandru Mifsud
We study random walks on dynamically evolving graphs, where the environment is given by a time-dependent subset of the edges of an underlying graph. Concretely, following the recen…
Planting and MCMC Sampling from the Potts model
Andreas Galanis, Leslie Ann Goldberg, Paulina Smolarova
We consider the problem of sampling from the ferromagnetic -state Potts model on the random -regular graph with parameter . A key difficulty that arises in sampling fro…