DROPS

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.ITCS.2026.55

Universally Optimal Streaming Algorithm for Random Walks in Dense Graphs

Authors: Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena, and Zhijun Zhang

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

Sampling a random walk is a fundamental primitive in many graph applications. In the streaming model, it is known that sampling an L-step random walk on an n-vertex directed graph requires Ω(n L) space, implying that no sublinear-space streaming algorithm exists for general graphs. We show that sublinear algorithms are possible for the case of dense graphs, where every vertex has out-degree at least Ω(n). In particular, we give a one-pass turnstile streaming algorithm that uses only 𝒪̃(L) memory for such graphs. More broadly, for graphs with minimum out-degree at least d, our streaming algorithm samples a random walk using 𝒪̃(n/d ⋅ L) memory. We show that our algorithm is optimal in a strong "beyond worst-case" sense. To formalize this, we introduce the notion of universal optimality for graph streaming algorithms. Informally, a streaming algorithm is universally optimal if it performs (almost) as well as possible on every graph, assuming a worst-case choice of the streaming order. This notion of universal optimality is a key conceptual contribution of our work.

Cite as

Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena, and Zhijun Zhang. Universally Optimal Streaming Algorithm for Random Walks in Dense Graphs. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 55:1-55:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{efremenko_et_al:LIPIcs.ITCS.2026.55,
  author =	{Efremenko, Klim and Kol, Gillat and Saxena, Raghuvansh R. and Zhang, Zhijun},
  title =	{{Universally Optimal Streaming Algorithm for Random Walks in Dense Graphs}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{55:1--55:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.55},
  URN =		{urn:nbn:de:0030-drops-253423},
  doi =		{10.4230/LIPIcs.ITCS.2026.55},
  annote =	{Keywords: Random Walk, streaming Algorithm, universal Optimality}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.59

On Approximating the f-Divergence Between Two Ising Models

Authors: Weiming Feng and Yucheng Fu

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

The f-divergence is a fundamental notion that measures the difference between two distributions. In this paper, we study the problem of approximating the f-divergence between two Ising models, which is a generalization of recent work on approximating the TV-distance. Given two Ising models ν and μ, which are specified by their interaction matrices and external fields, the problem is to approximate the f-divergence D_f (ν ‖ μ) within an arbitrary relative error e^{±ε}. For χ^α-divergence with a constant integer α, we establish both algorithmic and hardness results. The algorithm works in a parameter regime that matches the hardness result. Our algorithm can be extended to other f-divergences such as α-divergence, Kullback-Leibler divergence, Rényi divergence, Jensen-Shannon divergence, and squared Hellinger distance.

Cite as

Weiming Feng and Yucheng Fu. On Approximating the f-Divergence Between Two Ising Models. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 59:1-59:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{feng_et_al:LIPIcs.ITCS.2026.59,
  author =	{Feng, Weiming and Fu, Yucheng},
  title =	{{On Approximating the f-Divergence Between Two Ising Models}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{59:1--59:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.59},
  URN =		{urn:nbn:de:0030-drops-253469},
  doi =		{10.4230/LIPIcs.ITCS.2026.59},
  annote =	{Keywords: Ising model, f-divergence, approximation algorithms, randomized algorithms}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.63

Perfect Simulation of Las Vegas Algorithms via Local Computation

Authors: Xinyu Fu, Yonggang Jiang, and Yitong Yin

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

The notion of Las Vegas algorithms was introduced by Babai (1979) and can be defined in two ways: - In Babai’s original definition, a randomized algorithm is called Las Vegas if it has a finitely bounded running time and certifiable random failure. - Another definition widely accepted today is that Las Vegas algorithms refer to zero-error randomized algorithms with random running times. The equivalence between the two definitions is straightforward. Specifically, for randomized algorithms with certifiable failures, repeatedly running the algorithm until no failure is encountered allows for faithful simulation of the correct output when it executes successfully. We show that a similar perfect simulation can also be achieved in distributed local computation. Specifically, in the LOCAL model, with a polylogarithmic overhead in time complexity, any Las Vegas algorithm with finitely bounded running time and locally certifiable failures can be converted to a zero error Las Vegas algorithm. This transformed algorithm faithfully reproduces the correct output of the original algorithm in successful executions. This is achieved by a reduction to a distributed sampling problem under the Lovász Local Lemma (LLL), where the objective is to sample from the joint distribution of random variables avoiding all bad events. We then design the first efficient algorithm to solve this sampling problem in the LOCAL model.

Cite as

Xinyu Fu, Yonggang Jiang, and Yitong Yin. Perfect Simulation of Las Vegas Algorithms via Local Computation. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 63:1-63:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fu_et_al:LIPIcs.ITCS.2026.63,
  author =	{Fu, Xinyu and Jiang, Yonggang and Yin, Yitong},
  title =	{{Perfect Simulation of Las Vegas Algorithms via Local Computation}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{63:1--63:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.63},
  URN =		{urn:nbn:de:0030-drops-253503},
  doi =		{10.4230/LIPIcs.ITCS.2026.63},
  annote =	{Keywords: Las Vegas algorithms, perfect simulation, Lov\'{a}sz Local Lemma, sampling}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.114

Zero-Freeness Is All You Need: A Weitz-Type FPTAS for the Entire Lee-Yang Zero-Free Region

Authors: Shuai Shao and Ke Shi

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

We present a Weitz-type FPTAS for the ferromagnetic Ising model across the entire Lee–Yang zero-free region, without relying on the strong spatial mixing (SSM) property. Our algorithm is Weitz-type for two reasons. First, it expresses the partition function as a telescoping product of ratios, with the key being to approximate each ratio. Second, it uses Weitz’s self-avoiding walk tree, and truncates it at logarithmic depth to give a good and efficient approximation. The key difference from the standard Weitz algorithm is that we approximate a carefully designed edge-deletion ratio instead of the marginal probability of a vertex being assigned a particular spin, ensuring our algorithm does not require SSM. Furthermore, by establishing local dependence of coefficients (LDC), we indeed prove a novel form of SSM for these edge-deletion ratios, which, in turn, implies the standard SSM for the random cluster model. This is the first SSM result for the random cluster model on general graphs, beyond lattices. Our proof of LDC is based on a new division relation, and we show such relations hold quite universally. This leads to a broadly applicable framework for proving LDC across a variety of models, including the Potts model, the hypergraph independence polynomial, and Holant problems. Combined with existing zero-freeness results for these models, we derive new SSM results for them.

Cite as

Shuai Shao and Ke Shi. Zero-Freeness Is All You Need: A Weitz-Type FPTAS for the Entire Lee-Yang Zero-Free Region. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 114:1-114:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{shao_et_al:LIPIcs.ITCS.2026.114,
  author =	{Shao, Shuai and Shi, Ke},
  title =	{{Zero-Freeness Is All You Need: A Weitz-Type FPTAS for the Entire Lee-Yang Zero-Free Region}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{114:1--114:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.114},
  URN =		{urn:nbn:de:0030-drops-254010},
  doi =		{10.4230/LIPIcs.ITCS.2026.114},
  annote =	{Keywords: Ferromagnetic Ising Model, Lee–Yang Theorem, Weitz-Type FPTAS, Strong Spatial Mixing, 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

Brief Announcement

DOI: 10.4230/LIPIcs.DISC.2025.60

Brief Announcement: Distributed Sparsest Cut via Eigenvalue Estimation

Authors: Yannic Maus and Tijn de Vos

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract

We give new, improved bounds for approximating the sparsest cut value or in other words the conductance ϕ of a graph in the CONGEST model. As our main result, we present an algorithm running in O(log² n/ϕ) rounds in which every vertex outputs a value ̃ ϕ satisfying ϕ ≤ ̃ ϕ ≤ √{2.01ϕ}. In most regimes, our algorithm improves significantly over the previously fastest algorithm for the problem [Chen, Meierhans, Probst Gutenberg, Saranurak; SODA 25]. Additionally, our result generalizes to k-way conductance. We obtain these results, by approximating the eigenvalues of the normalized Laplacian matrix L: = I-Deg^{-1/2}ADeg^ {-1/2}, where, A is the adjacency matrix and Deg is the diagonal matrix with the weighted degrees on the diagonal. We show our algorithms are near-optimal by proving a lower bound for computing the smallest non-trivial eigenvalue of L, even in the stronger LOCAL model The previous state of the art sparsest cut algorithm is in the technical realm of expander decompositions. Our algorithms, on the other hand, are relatively simple and easy to implement. At the core, they rely on the well-known power method, which comes down to repeatedly multiplying the Laplacian with a vector. This operation can be performed in a single round in the CONGEST model. All our algorithms apply to weighted, undirected graphs. Our lower bounds apply even in unweighted graphs.

Cite as

Yannic Maus and Tijn de Vos. Brief Announcement: Distributed Sparsest Cut via Eigenvalue Estimation. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 60:1-60:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{maus_et_al:LIPIcs.DISC.2025.60,
  author =	{Maus, Yannic and de Vos, Tijn},
  title =	{{Brief Announcement: Distributed Sparsest Cut via Eigenvalue Estimation}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{60:1--60:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.60},
  URN =		{urn:nbn:de:0030-drops-248763},
  doi =		{10.4230/LIPIcs.DISC.2025.60},
  annote =	{Keywords: CONGEST, Sparsest Cut, Laplacian, Eigenvalues, Spectral Graph Theory}
}

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.42

On the Spectral Expansion of Monotone Subsets of the Hypercube

Authors: Yumou Fei and Renato Ferreira Pinto Jr.

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

Abstract

We study the spectral gap of subgraphs of the hypercube induced by monotone subsets of vertices. For a monotone subset A ⊆ {0,1}ⁿ of density μ(A), the previous best lower bound on the spectral gap, due to Cohen [Cohen, 2016], was γ ≳ μ(A)/n², improving upon the earlier bound γ ≳ μ(A)²/n² established by Ding and Mossel [Ding and Mossel, 2014]. In this paper, we prove the optimal lower bound γ ≳ μ(A)/n. As a corollary, we improve the mixing time upper bound of the random walk on constant-density monotone sets from O(n³), as shown by Ding and Mossel, to O(n²). Along the way, we develop two new inequalities that may be of independent interest: (1) a directed L²-Poincaré inequality on the hypercube, and (2) an "approximate" FKG inequality for monotone sets.

Cite as

Yumou Fei and Renato Ferreira Pinto Jr.. On the Spectral Expansion of Monotone Subsets of the Hypercube. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 42:1-42:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fei_et_al:LIPIcs.APPROX/RANDOM.2025.42,
  author =	{Fei, Yumou and Ferreira Pinto Jr., Renato},
  title =	{{On the Spectral Expansion of Monotone Subsets of the Hypercube}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{42:1--42:24},
  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.42},
  URN =		{urn:nbn:de:0030-drops-244081},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.42},
  annote =	{Keywords: Random walks, mixing time, FKG inequality, Poincar\'{e} inequality, directed isoperimetry}
}

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.46

Efficient Parallel Ising Samplers via Localization Schemes

Authors: Xiaoyu Chen, Hongyang Liu, Yitong Yin, and Xinyuan Zhang

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

Abstract

We introduce efficient parallel algorithms for sampling from the Gibbs distribution and estimating the partition function of Ising models. These algorithms achieve parallel efficiency, with polylogarithmic depth and polynomial total work, and are applicable to Ising models in the following regimes: (1) Ferromagnetic Ising models with external fields; (2) Ising models with interaction matrix J of operator norm ‖J‖₂ < 1. Our parallel Gibbs sampling approaches are based on localization schemes, which have proven highly effective in establishing rapid mixing of Gibbs sampling. In this work, we employ two such localization schemes to obtain efficient parallel Ising samplers: the field dynamics induced by negative-field localization, and restricted Gaussian dynamics induced by stochastic localization. This shows that localization schemes are powerful tools, not only for achieving rapid mixing but also for the efficient parallelization of Gibbs sampling.

Cite as

Xiaoyu Chen, Hongyang Liu, Yitong Yin, and Xinyuan Zhang. Efficient Parallel Ising Samplers via Localization Schemes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 46:1-46:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.APPROX/RANDOM.2025.46,
  author =	{Chen, Xiaoyu and Liu, Hongyang and Yin, Yitong and Zhang, Xinyuan},
  title =	{{Efficient Parallel Ising Samplers via Localization Schemes}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{46:1--46: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.46},
  URN =		{urn:nbn:de:0030-drops-244129},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.46},
  annote =	{Keywords: Localization scheme, parallel sampling, Ising model}
}

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.60

Sink-Free Orientations: A Local Sampler with Applications

Authors: Konrad Anand, Graham Freifeld, Heng Guo, Chunyang Wang, and Jiaheng Wang

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

Abstract

For sink-free orientations in graphs of minimum degree at least 3, we show that there is a deterministic approximate counting algorithm that runs in time O((n^33/ε^32)log(n/ε)), a near-linear time sampling algorithm, and a randomised approximate counting algorithm that runs in time O((n/ε)²log(n/ε)), where n denotes the number of vertices of the input graph and 0 < ε < 1 is the desired accuracy. All three algorithms are based on a local implementation of the sink popping method (Cohn, Pemantle, and Propp, 2002) under the partial rejection sampling framework (Guo, Jerrum, and Liu, 2019).

Cite as

Konrad Anand, Graham Freifeld, Heng Guo, Chunyang Wang, and Jiaheng Wang. Sink-Free Orientations: A Local Sampler with Applications. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 60:1-60:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{anand_et_al:LIPIcs.APPROX/RANDOM.2025.60,
  author =	{Anand, Konrad and Freifeld, Graham and Guo, Heng and Wang, Chunyang and Wang, Jiaheng},
  title =	{{Sink-Free Orientations: A Local Sampler with Applications}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{60:1--60:19},
  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.60},
  URN =		{urn:nbn:de:0030-drops-244267},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.60},
  annote =	{Keywords: Sink-free orientations, local sampling, deterministic counting}
}

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.14

Improved Lower Bounds on Multiflow-Multicut Gaps

Authors: Sina Kalantarzadeh and Nikhil Kumar

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

Abstract

Given a set of source-sink pairs, the maximum multiflow problem asks for the maximum total amount of flow that can be feasibly routed between them. The minimum multicut, a dual problem to multiflow, seeks the minimum-cost set of edges whose removal disconnects all the source-sink pairs. It is easy to see that the value of the minimum multicut is at least that of the maximum multiflow, and their ratio is called the multiflow-multicut gap. The classical max-flow min-cut theorem states that when there is only one source-sink pair, the gap is exactly one. However, in general, it is well known that this gap can be arbitrarily large. In this paper, we study this gap for classes of planar graphs and establish improved lower bound results. In particular, we show that this gap is at least 20/9 for the class of planar graphs, improving upon the decades-old lower bound of 2. More importantly, we develop new techniques for proving such a lower bound, which may be useful in other settings as well.

Cite as

Sina Kalantarzadeh and Nikhil Kumar. Improved Lower Bounds on Multiflow-Multicut Gaps. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kalantarzadeh_et_al:LIPIcs.APPROX/RANDOM.2025.14,
  author =	{Kalantarzadeh, Sina and Kumar, Nikhil},
  title =	{{Improved Lower Bounds on Multiflow-Multicut Gaps}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{14:1--14:18},
  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.14},
  URN =		{urn:nbn:de:0030-drops-243803},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.14},
  annote =	{Keywords: Approximation Algorithms, Randomized Algorithms, Linear Programming, Graph Algorithms, Scheduling, Multicut, Multiflow}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2025.21

On the Performance of Mildly Greedy Players in k-Coloring Games

Authors: Vittorio Bilò, Andrea D'Ascenzo, Mattia D'Emidio, and Giuseppe F. Italiano

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract

We study the performance of mildly greedy players in k-coloring games, a relevant subclass of anti-coordination games. A mildly greedy player is a selfish agent who is willing to deviate from a certain strategy profile only if her payoff improves by a factor of more than ε, for some given ε ≥ 0. In presence of mildly greedy players, stability is captured by the concept of (1+ε)-approximate Nash equilibrium. In this paper, we first show that, for any k-coloring game, the (1+ε)-approximate price of anarchy, i.e., the price of anarchy of (1+ε)-approximate pure Nash equilibria, is at least (k-1)/((k-1)ε +k), and that this bound is tight for any ε ≥ 0. Then, we evaluate the approximation ratio of the solutions achieved after a (1 + ϵ)-approximate one-round walk starting from any initial strategy profile, where a (1 + ϵ)-approximate one-round walk is a sequence of (1 + ε)-approximate best-responses, one for each player. We provide a lower bound of min{(k-2)/k, (k-1)/((k-1)ε+k)} on this ratio, for any ε ≥ 0 and k ≥ 5; for the cases of k = 3 and k = 4, we give finer bounds depending on ε. Our work generalizes the results known for cut games, the special case of k-coloring games restricted to k = 2.

Cite as

Vittorio Bilò, Andrea D'Ascenzo, Mattia D'Emidio, and Giuseppe F. Italiano. On the Performance of Mildly Greedy Players in k-Coloring Games. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 21:1-21:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.MFCS.2025.21,
  author =	{Bil\`{o}, Vittorio and D'Ascenzo, Andrea and D'Emidio, Mattia and Italiano, Giuseppe F.},
  title =	{{On the Performance of Mildly Greedy Players in k-Coloring Games}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{21:1--21:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.21},
  URN =		{urn:nbn:de:0030-drops-241287},
  doi =		{10.4230/LIPIcs.MFCS.2025.21},
  annote =	{Keywords: Coloring games, (Approximate) Nash Equilibria, Price of Anarchy}
}

Document

DOI: 10.4230/LIPIcs.CP.2025.24

The Work Task Variation Problem

Authors: Mikael Z. Lagerkvist and Magnus Rattfeldt

Published in: LIPIcs, Volume 340, 31st International Conference on Principles and Practice of Constraint Programming (CP 2025)

Abstract

This paper introduces the Work Task Variation (WTV) problem, a novel scheduling post-processing challenge focused on improving worker shift quality by rearranging tasks within their assigned time slots. The objective is to avoid excessively short or long durations of specific task types, creating smoother and more ergonomic work patterns. We present RosterLogic Variation, a constraint-based local search (CBLS) inspired solver originally developed at Optischedule and successfully deployed in real-world retail settings. This solver rapidly improves existing schedules using tailored invariants and heuristics. We also provide a complete MiniZinc model and a set of generated realistic publicly available benchmark instances. We compare our solver’s performance with that of modern CP solvers using the MiniZinc model. Contemporary state-of-the-art CP solvers are approaching the interactive performance of our CBLS solver for coarse planning, representing a significant advancement since the original design and implementation of our solver.

Cite as

Mikael Z. Lagerkvist and Magnus Rattfeldt. The Work Task Variation Problem. In 31st International Conference on Principles and Practice of Constraint Programming (CP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 340, pp. 24:1-24:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lagerkvist_et_al:LIPIcs.CP.2025.24,
  author =	{Lagerkvist, Mikael Z. and Rattfeldt, Magnus},
  title =	{{The Work Task Variation Problem}},
  booktitle =	{31st International Conference on Principles and Practice of Constraint Programming (CP 2025)},
  pages =	{24:1--24:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-380-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{340},
  editor =	{de la Banda, Maria Garcia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2025.24},
  URN =		{urn:nbn:de:0030-drops-238850},
  doi =		{10.4230/LIPIcs.CP.2025.24},
  annote =	{Keywords: Constraint-Based Local Search, Constraint Programming, Metaheuristics, Scheduling}
}

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}
}

23 Search Results for "Sinclair, Alistair"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message