4 papers
Triangle-Free Coloring in LOCAL via Resilient Lovász Local Lemma
Peter Davies-Peck, Xusheng Zhang
The Lovász Local Lemma (LLL) is a probabilistic tool that has been shown to be of central importance in the study of distributed algorithms. For example, the constructive LLL is kn…
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…
Uniqueness and Mixing in the Low-Temperature Random-Cluster Model on Trees and Random Graphs
Antonio Blanca, Reza Gheissari, Heehyun Park +1
We study the random-cluster model on trees and treelike graphs at low temperatures. This is a model of dependent percolation parametrized by an edge probability and a…
One-Shot Learning for k-SAT
Andreas Galanis, Leslie Ann Goldberg, Xusheng Zhang
Consider a -SAT formula where every variable appears at most times. Let be a satisfying assignment, sampled proportionally to where is the number…