6 Search Results for "Yang, Linji"

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
DOI: 10.4230/LIPIcs.FSTTCS.2025.17
Cutoff for the Swendsen–Wang Dynamics on the Complete Graph

Authors: Antonio Blanca and Zhezheng Song

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
We study the speed of convergence of the Swendsen-Wang (SW) dynamics for the q-state ferromagnetic Potts model on the n-vertex complete graph, known as the mean-field model. The SW dynamics was introduced as an attractive alternative to the local Glauber dynamics, often offering faster convergence rates to stationarity in a variety of settings. A series of works have characterized the asymptotic behavior of the speed of convergence of the mean-field SW dynamics for all q ≥ 2 and all values of the inverse temperature parameter β > 0. In particular, it is known that when β > q the mixing time of the SW dynamics is Θ(log n). We strengthen this result by showing that for all β > q, there exists a constant c(β,q) > 0 such that the mixing time of the SW dynamics is c(β,q) log n + Θ(1). This implies that the mean-field SW dynamics exhibits the cutoff phenomenon in this temperature regime, demonstrating that this Markov chain undergoes a sharp transition from "far from stationarity" to "well-mixed" within a narrow Θ(1) time window. The presence of cutoff is algorithmically significant, as simulating the chain for fewer steps than its mixing time could lead to highly biased samples.
Cite as

Antonio Blanca and Zhezheng Song. Cutoff for the Swendsen–Wang Dynamics on the Complete Graph. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 17:1-17:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{blanca_et_al:LIPIcs.FSTTCS.2025.17,
  author =	{Blanca, Antonio and Song, Zhezheng},
  title =	{{Cutoff for the Swendsen–Wang Dynamics on the Complete Graph}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{17:1--17:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.17},
  URN =		{urn:nbn:de:0030-drops-250987},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.17},
  annote =	{Keywords: Markov chains, mixing times, cutoff phenomenon, Potts model, mean-field}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.47
Time Lower Bounds for the Metropolis Process and Simulated Annealing

Authors: Zongchen Chen, Dan Mikulincer, Daniel Reichman, and Alexander S. Wein

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

Abstract
The Metropolis process (MP) and Simulated Annealing (SA) are stochastic local search heuristics that are often used in solving combinatorial optimization problems. Despite significant interest, there are very few theoretical results regarding the quality of approximation obtained by MP and SA (with polynomially many iterations) for NP-hard optimization problems. We provide rigorous lower bounds for MP and SA with respect to the classical maximum independent set problem when the algorithms are initialized from the empty set. We establish the existence of a family of graphs for which both MP and SA fail to find approximate solutions in polynomial time. More specifically, we show that for any ε ∈ (0,1) there are n-vertex graphs for which the probability SA (when limited to polynomially many iterations) will approximate the optimal solution within ratio Ω(1/n^{1-ε}) is exponentially small. Our lower bounds extend to graphs of constant average degree d, illustrating the failure of MP to achieve an approximation ratio of Ω(log(d)/d) in polynomial time. In some cases, our lower bounds apply even when the temperature is chosen adaptively. Finally, we prove exponential-time lower bounds when the inputs to these algorithms are bipartite graphs, and even trees, which are known to admit polynomial-time algorithms for the independent set problem.
Cite as

Zongchen Chen, Dan Mikulincer, Daniel Reichman, and Alexander S. Wein. Time Lower Bounds for the Metropolis Process and Simulated Annealing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 47:1-47:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.APPROX/RANDOM.2025.47,
  author =	{Chen, Zongchen and Mikulincer, Dan and Reichman, Daniel and Wein, Alexander S.},
  title =	{{Time Lower Bounds for the Metropolis Process and Simulated Annealing}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{47:1--47:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.47},
  URN =		{urn:nbn:de:0030-drops-244138},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.47},
  annote =	{Keywords: Metropolis Process, Simulated Annealing, Independent Set}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.68
Rapid Mixing via Coupling Independence for Spin Systems with Unbounded Degree

Authors: Xiaoyu Chen and Weiming Feng

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

Abstract
We develop a new framework to prove the mixing or relaxation time for the Glauber dynamics on spin systems with unbounded degree. It works for general spin systems including both 2-spin and multi-spin systems. As applications for this approach: - We prove the optimal O(n) relaxation time for the Glauber dynamics of random q-list-coloring on an n-vertices triangle-tree graph with maximum degree Δ such that q/Δ > α^⋆, where α^⋆ ≈ 1.763 is the unique positive solution of the equation α = exp(1/α). This improves the n^{1+o(1)} relaxation time for Glauber dynamics obtained by the previous work of Jain, Pham, and Vuong (2022). Besides, our framework can also give a near-linear time sampling algorithm under the same condition. - We prove the optimal O(n) relaxation time and near-optimal Õ(n) mixing time for the Glauber dynamics on hardcore models with parameter λ in balanced bipartite graphs such that λ < λ_c(Δ_L) for the max degree Δ_L in left part and the max degree Δ_R of right part satisfies Δ_R = O(Δ_L). This improves the previous result by Chen, Liu, and Yin (2023). At the heart of our proof is the notion of coupling independence which allows us to consider multiple vertices as a huge single vertex with exponentially large domain and do a "coarse-grained" local-to-global argument on spin systems. The technique works for general (multi) spin systems and helps us obtain some new comparison results for Glauber dynamics.
Cite as

Xiaoyu Chen and Weiming Feng. Rapid Mixing via Coupling Independence for Spin Systems with Unbounded Degree. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 68:1-68:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.APPROX/RANDOM.2025.68,
  author =	{Chen, Xiaoyu and Feng, Weiming},
  title =	{{Rapid Mixing via Coupling Independence for Spin Systems with Unbounded Degree}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{68:1--68:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.68},
  URN =		{urn:nbn:de:0030-drops-244345},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.68},
  annote =	{Keywords: coupling independence, Glauber dynamics, mixing times, relaxation times, spin systems}
}
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
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.677
Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results

Authors: Andreas Galanis, Daniel Stefankovic, Eric Vigoda, and Linji Yang

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

Abstract
Recent results establish for the hard-core model (and more generally for 2-spin antiferromagnetic systems) that the computational complexity of approximating the partition function on graphs of maximum degree D undergoes a phase transition that coincides with the uniqueness/non-uniqueness phase transition on the infinite D-regular tree. For the ferromagnetic Potts model we investigate whether analogous hardness results hold. Goldberg and Jerrum showed that approximating the partition function of the ferromagnetic Potts model is at least as hard as approximating the number of independent sets in bipartite graphs, so-called #BIS-hardness. We improve this hardness result by establishing it for bipartite graphs of maximum degree D. To this end, we first present a detailed picture for the phase diagram for the infinite D-regular tree, giving a refined picture of its first-order phase transition and establishing the critical temperature for the coexistence of the disordered and ordered phases. We then prove for all temperatures below this critical temperature (corresponding to the region where the ordered phase "dominates") that it is #BIS-hard to approximate the partition function on bipartite graphs of maximum degree D. The #BIS-hardness result uses random bipartite regular graphs as a gadget in the reduction. The analysis of these random graphs relies on recent results establishing connections between the maxima of the expectation of their partition function, attractive fixpoints of the associated tree recursions, and induced matrix norms. In this paper we extend these connections to random regular graphs for all ferromagnetic models. Using these connections, we establish the Bethe prediction for every ferromagnetic spin system on random regular graphs, which says roughly that the expectation of the log of the partition function Z is the same as the log of the expectation of Z. As a further consequence of our results, we prove for the ferromagnetic Potts model that the Swendsen-Wang algorithm is torpidly mixing (i.e., exponentially slow convergence to its stationary distribution) on random D-regular graphs at the critical temperature for sufficiently large q.
Cite as

Andreas Galanis, Daniel Stefankovic, Eric Vigoda, and Linji Yang. Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 677-691, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{galanis_et_al:LIPIcs.APPROX-RANDOM.2014.677,
  author =	{Galanis, Andreas and Stefankovic, Daniel and Vigoda, Eric and Yang, Linji},
  title =	{{Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{677--691},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.677},
  URN =		{urn:nbn:de:0030-drops-47319},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.677},
  annote =	{Keywords: Ferromagnetic Potts model, approximate counting, spin systems, phase transition, random regular graphs}
}
  • Refine by Type
  • 6 Document/PDF
  • 5 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 4 2025
  • 1 2014

  • Refine by Author
  • 3 Galanis, Andreas
  • 2 Goldberg, Leslie Ann
  • 2 Smolarova, Paulina
  • 1 Blanca, Antonio
  • 1 Chen, Xiaoyu
  • Show More...

  • Refine by Series/Journal
  • 6 LIPIcs

  • Refine by Classification
  • 3 Mathematics of computing → Random graphs
  • 2 Mathematics of computing → Gibbs sampling
  • 2 Mathematics of computing → Markov-chain Monte Carlo methods
  • 2 Theory of computation → Random walks and Markov chains
  • 1 Mathematics of computing → Markov processes
  • Show More...

  • Refine by Keyword
  • 3 Glauber dynamics
  • 2 Potts model
  • 2 approximate counting
  • 2 approximate sampling
  • 2 mixing times
  • Show More...

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-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact