Search Results

Documents authored by Smolarova, Paulina

Document
DOI: 10.4230/LIPIcs.STACS.2026.39
Planting and MCMC Sampling from the Potts Model

Authors: Andreas Galanis, Leslie Ann Goldberg, and Paulina Smolarova

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
We consider the problem of sampling from the ferromagnetic q-state Potts model on the random d-regular graph with parameter β > 0. A key difficulty that arises in sampling from the model is the existence of a "metastability" window β ∈ (β_u,β_u'), where roughly the distribution has two competing modes, the so-called disordered and ordered phases. This causes classical Markov-chain algorithms to be slow mixing from worst-case initialisations. Nevertheless, Helmuth, Jenssen and Perkins (SODA '19) designed a sampling algorithm that works for all β, when d ≥ 5 and q = d^{Ω(d)}, using polymers and cluster expansion methods; more recently, their analysis technique has been adapted to show that a Markov chain (random-cluster dynamics) mixes fast when initialised appropriately, in the same regime of q,d,β. Despite these positive algorithmic results, a well-known bottleneck behind cluster-expansion arguments is that they inherently only work for large q, whereas it is widely conjectured that sampling on the random d-regular graph is possible for all q,d ≥ 3. The only result so far that applies to general q,d ≥ 3 is by Blanca and Gheissari who showed that the random-cluster dynamics mixes fast in the "uniqueness" regime β < β_u where roughly only the disordered mode exists. For β ≥ β_u however, a second subdominant mode emerges creating bottlenecks and giving rise to correlations which have been hard to handle, especially for small values of q and d. Our main contribution is to perform a delicate analysis of the Potts distribution and the random-cluster dynamics that goes beyond the threshold β_u. We use planting as the main tool, a technique used in the analysis of random CSPs to capture how the space of solutions is correlated with the structure of the random instance. While planting arguments provide only weak sampling guarantees generically, here we instead combine planting with the analysis of random-cluster dynamics to obtain significantly stronger guarantees. We are thus able to show that the random-cluster dynamics initialised from all-out mixes fast for all integers q,d ≥ 3 beyond the uniqueness threshold β_u, all the way to the optimal threshold β_c ∈ (β_u,β_u') where the dominant mode switches from disordered to ordered. A more involved analysis also applies to the ordered regime β > β_c where we obtain an algorithm for all d ≥ 3 and q ≥ (5d)⁵, improving significantly upon the previous range of q,d by Carlson, Davies, Fraiman, Kolla, Potukuchi, and Yap (FOCS'22).
Cite as

Andreas Galanis, Leslie Ann Goldberg, and Paulina Smolarova. Planting and MCMC Sampling from the Potts Model. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 39:1-39:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{galanis_et_al:LIPIcs.STACS.2026.39,
  author =	{Galanis, Andreas and Goldberg, Leslie Ann and Smolarova, Paulina},
  title =	{{Planting and MCMC Sampling from the Potts Model}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{39:1--39:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.39},
  URN =		{urn:nbn:de:0030-drops-255280},
  doi =		{10.4230/LIPIcs.STACS.2026.39},
  annote =	{Keywords: approximate sampling, Glauber dynamics, Potts model, random cluster model}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.83
Low-Temperature Sampling on Sparse Random Graphs

Authors: Andreas Galanis, Leslie Ann Goldberg, and Paulina Smolarova

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We consider sampling in the so-called low-temperature regime, which is typically characterised by non-local behaviour and strong global correlations. Canonical examples include sampling independent sets on bipartite graphs and sampling from the ferromagnetic q-state Potts model. Low-temperature sampling is computationally intractable for general graphs, but recent advances based on the polymer method have made significant progress for graph families that exhibit certain expansion properties that reinforce the correlations, including for example expanders, lattices and dense graphs. One of the most natural graph classes that has so far escaped this algorithmic framework is the class of sparse Erdős-Rényi random graphs whose expansion only manifests for sufficiently large subsets of vertices; small sets of vertices on the other hand have vanishing expansion which makes them behave independently from the bulk of the graph and therefore weakens the correlations. At a more technical level, the expansion of small sets is crucial for establishing the Kotecky-Priess condition which underpins the applicability of the framework. Our main contribution is to develop the polymer method in the low-temperature regime for sparse random graphs. As our running example, we use the Potts and random-cluster models on G(n,d/n) for d = Θ(1), where we show a polynomial-time sampling algorithm for all sufficiently large q and d, at all temperatures. Our approach applies more generally for models that are monotone. Key to our result is a simple polymer definition that blends easily with the connectivity properties of the graph and allows us to show that polymers have size at most O(log n).
Cite as

Andreas Galanis, Leslie Ann Goldberg, and Paulina Smolarova. Low-Temperature Sampling on Sparse Random Graphs. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 83:1-83:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{galanis_et_al:LIPIcs.ICALP.2025.83,
  author =	{Galanis, Andreas and Goldberg, Leslie Ann and Smolarova, Paulina},
  title =	{{Low-Temperature Sampling on Sparse Random Graphs}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{83:1--83:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.83},
  URN =		{urn:nbn:de:0030-drops-234606},
  doi =		{10.4230/LIPIcs.ICALP.2025.83},
  annote =	{Keywords: approximate counting, Glauber dynamics, random cluster model, approximate sampling, Erd\H{o}s-R\'{e}nyi Graphs}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.64
Sampling from the Random Cluster Model on Random Regular Graphs at All Temperatures via Glauber Dynamics

Authors: Andreas Galanis, Leslie Ann Goldberg, and Paulina Smolarova

Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)

Abstract
We consider the performance of Glauber dynamics for the random cluster model with real parameter q > 1 and temperature β > 0. Recent work by Helmuth, Jenssen and Perkins detailed the ordered/disordered transition of the model on random Δ-regular graphs for all sufficiently large q and obtained an efficient sampling algorithm for all temperatures β using cluster expansion methods. Despite this major progress, the performance of natural Markov chains, including Glauber dynamics, is not yet well understood on the random regular graph, partly because of the non-local nature of the model (especially at low temperatures) and partly because of severe bottleneck phenomena that emerge in a window around the ordered/disordered transition. Nevertheless, it is widely conjectured that the bottleneck phenomena that impede mixing from worst-case starting configurations can be avoided by initialising the chain more judiciously. Our main result establishes this conjecture for all sufficiently large q (with respect to Δ). Specifically, we consider the mixing time of Glauber dynamics initialised from the two extreme configurations, the all-in and all-out, and obtain a pair of fast mixing bounds which cover all temperatures β, including in particular the bottleneck window. Our result is inspired by the recent approach of Gheissari and Sinclair for the Ising model who obtained a similar-flavoured mixing-time bound on the random regular graph for sufficiently low temperatures. To cover all temperatures in the RC model, we refine appropriately the structural results of Helmuth, Jenssen and Perkins about the ordered/disordered transition and show spatial mixing properties "within the phase", which are then related to the evolution of the chain.
Cite as

Andreas Galanis, Leslie Ann Goldberg, and Paulina Smolarova. Sampling from the Random Cluster Model on Random Regular Graphs at All Temperatures via Glauber Dynamics. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 64:1-64:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{galanis_et_al:LIPIcs.APPROX/RANDOM.2023.64,
  author =	{Galanis, Andreas and Goldberg, Leslie Ann and Smolarova, Paulina},
  title =	{{Sampling from the Random Cluster Model on Random Regular Graphs at All Temperatures via Glauber Dynamics}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{64:1--64:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.64},
  URN =		{urn:nbn:de:0030-drops-188896},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.64},
  annote =	{Keywords: approximate counting, Glauber dynamics, random cluster model, approximate sampling, random regular graphs}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact