1 citations · 1 across the 4 of their papers we have counts for
5 papers · 1 filter
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…
Sampling Colorings and Independent Sets of Random Regular Bipartite Graphs in the Non-Uniqueness Region
Zongchen Chen, Andreas Galanis, Daniel Štefankovič +1
For spin systems, such as the -colorings and independent-set models, approximating the partition function in the so-called non-uniqueness region, where the model exhibits long-r…
Rapid Mixing for Colorings via Spectral Independence
Zongchen Chen, Andreas Galanis, Daniel Štefankovič +1
The spectral independence approach of Anari et al. (2020) utilized recent results on high-dimensional expanders of Alev and Lau (2020) and established rapid mixing of the Glauber d…
Fast algorithms for general spin systems on bipartite expanders
Andreas Galanis, Leslie Ann Goldberg, James Stewart
A spin system is a framework in which the vertices of a graph are assigned spins from a finite set. The interactions between neighbouring spins give rise to weights, so a spin assi…
Fast algorithms at low temperatures via Markov chains
Zongchen Chen, Andreas Galanis, Leslie Ann Goldberg +3
We define a discrete-time Markov chain for abstract polymer models and show that under sufficient decay of the polymer weights, this chain mixes rapidly. We apply this Markov chain…