Congested Clique Counting for Local Gibbs Distributions
Joshua Z. Sobel · 2025
Read Congested Clique Counting for Local Gibbs Distributions by Joshua Z. Sobel (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-13083.txt.
Introduction
Sobel gives in twenty twenty-five the first fast counting method for a broad family of probability distributions in a fully connected distributed network model. Counting and sampling are known to be linked, so a recent parallel sampling method opened the door. His scheme draws many random samples from a distributed chain at once, borrowing tricks from distributed triangle counting and matrix methods.
The headline case counts graph colourings within a small error when the colour count clears a bar tied to the busiest node. The same runtime covers general distributions on graphs that mix fast and depend only locally. A special case, counting weighted independent sets, runs far faster still. The sampling tool may serve other tasks needing many samples.
Catalog record
| CREATOR | Joshua Z. Sobel |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 43 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-13083
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Congested Clique Counting for Local Gibbs Distributions Joshua Z. Sobel Abstract There are well established reductions between combinatorial sampling and counting problems (Jerrum, Valiant, Vazirani TCS 1986). Building off of a very recent parallel algorithm utilizing this connection (Liu, Yin, Zhang arxiv 2024), we demonstrate the first approximate counting algorithm in the CongestedClique for a wide range of problems. Most interestingly, we present an algorithm for approximating the number of q q -colorings of a graph within ϵ \epsilon -multiplicative error, when q > α Δ q>\alpha\Delta for any constant α > 2 \alpha>2 , in O ~ ( n 1 / 3 ϵ 2 ) \tilde{O}\big(\frac{n^{1/3}}{\epsilon^{2}}\big) rounds. More generally, we achieve a runtime of O ~ ( n 1 / 3 ϵ 2 ) \tilde{O}\big(\frac{n^{1/3}}{\epsilon^{2}}\big) rounds for approximating the partition function of Gibbs distributions defined over graphs when simple locality and fast mixing conditions hold. Gibbs distributions are widely used in fields such as machine learning and statistical physics. We obtain our result by providing an algorithm to draw n n random samples from a distributed Markov chain in parallel, using similar ideas to triangle counting (Dolev, Lenzen, Peled DISC 2012) and semiring matrix multiplication (Censor-Hillel, Kaski, Korhonen, Lenzen, Paz, Suomela PODC 2015). Aside from counting problems, this result may be interesting for other applications requiring a large number of samples. In the special case of estimating the partition function of the hardcore model, also known as counting weighted independent sets, we can do even better and achieve an O ~ ( 1 ϵ 2 ) \tilde{O}\big(\frac{1}{\epsilon^{2}}\big) round algorithm, when the fugacity λ ≤ α Δ − 1 \lambda\leq\frac{\alpha}{\Delta-1} , where α \alpha is an arbitrary constant less than 1 1 . Department of Computer Science, University of Iowa, Iowa City, Iowa, [email protected]://orcid.org/0009-0004-7482-0754 Thanks to Sriram Pemmaraju for suggestions and discussions. ccs Theory of computation Distributed algorithms ccs Theory of computation Random walks and Markov chains keywords Distributed Sampling, Approximate Counting, Markov Chains, Gibbs Distributions † † runningauthor: J. Z. Sobel † † copyright: Joshua Z. Sobel † † funding: The author was partially supported during this project by National Science Foundation grants 1955939 and 2402835. † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction In a pioneering work, Valiant proposed the computational complexity class #P [ 27 ] . Problems in #P are the counting variants of decision problems in NP; for example, counting the number of satisfying 3-SAT assignments or counting the number of proper vertex colorings of a graph using at most q colors ( q -colorings). Unfortunately, Valiant established that even when a decision problem is in P , such as determining whether a bipartite graph has a perfect matching, the corresponding counting problem can be NP-hard. Thus for most counting problems, we need to settle for \epsilon multiplicative approximation rather than exact counting. The goal is to estimate a true count X by \hat{X} , such that (1-\epsilon)X\leq\hat{X}\leq(1+\epsilon)X with probability at least \frac{3}{4} . 1 1 1 By the standard median trick, 3/4 can be boosted to any constant less than one. The typical method for approximate counting involves drawing random samples that are solutions to the corresponding search problem. In other words, we can count the number of colorings of a graph by sampling random colorings. This approach dates back to Jerrum, Valiant, and Vazirani [ 17 ] showing that for a wide class of problems, most notably joint distributions on a graph (e.g. colorings and matchings), fully polynomial-time randomized approximate counting is inter-reducible with polynomial-time approximate sampling. 2 2 2 The precise result is slightly more complex and requires sampling from both the original distribution and derived conditional distributions. The initial reduction from counting to sampling [ 17 ] requires drawing a very large number of samples; this has been improved over several subsequent works [ 16 , 1 , 28 , 20 ] . In particular, when considering Gibbs distributions defined over graphs with n vertices and meeting mild conditions, Štefankovič, Vempala, and Vigoda [ 28 ] showed that counting can be accomplished by taking \tilde{O}\big(\frac{n}{\epsilon^{2}}\big) samples. 3 3 3 As we will explain later, for an arbitrary Gibbs distribution, counting refers to estimating the partition function. This is a generalization of counting the size of a set. Gibbs distributions originated in physics, and generalize many problems such as the uniform distribution of q -colorings. In computer science, they have found uses in many areas such as machine learning [ 25 ] , image processing [ 13 ] , and even computational biology [ 22 ] . Unfortunately, the algorithm from [ 28 ] cannot be fully parallelized, as samples drawn later depend on samples drawn earlier. It does seem possible to obtain an \tilde{O}(\frac{\sqrt{n}}{\epsilon^{2}}) round CongestedClique implementation of this algorithm; however, our results show we can do much better. Very recently, Liu, Yin, and Zhang [ 20 ] also showed that for many Gibbs distributions defined over graphs counting can be done using \tilde{O}\big(\frac{n}{\epsilon^{2}}\big) total samples, but in their approach every sample can be taken in parallel. This implies that counting in the CongestedClique reduces to quickly drawing \tilde{O}\big(\frac{n}{\epsilon^{2}}\big) samples. From existing work, [ 10 , 12 , 8 ] , we know that for many Gibbs distributions drawing a single sample within total variation distance error of \delta can be done in O(\log\frac{n}{\delta}) CongestedClique rounds, using the distributed Metropolis-Hastings Markov chain. For Gibbs distributions that we call local , we identify a novel structural similarity between simulating one transition of n instances of the Markov chain and semiring matrix multiplication. In particular, utilizing the approach of Dolev, Lenzen, and Peled [ 6 ] for triangle counting and Censor-Hillel, Kaski, Korhonen, Lenzen, Paz, and Suomela [ 3 ] for semiring matrix multiplication, we can simulate one transition of n instances of the Markov chain in O(n^{1/3}) rounds. Altogether, this shows that for local Gibbs distributions we can count in \tilde{O}\big(\frac{n^{1/3}}{\epsilon^{2}}\big) CongestedClique rounds when the Markov chain has an O(\log\frac{n}{\delta}) mixing time. 1.1 Main Results Our central contribution is an algorithm to draw many samples at once from the distributed Metropolis-Hastings Markov chain. Beyond counting, this result may be useful in other algorithms where several samples are needed. Theorem 1 . One transition can be simulated for n instances of the distributed Metropolis-Hastings chain in O(n^{1/3}) rounds. As a corollary to the previous theorem and the results of [ 20 ] , under mild locality and mixing conditions which we will describe later, there is an \tilde{O}\big(\frac{n^{1/3}}{\epsilon^{2}}\big) round counting algorithm. As the most interesting example, we obtain a fast algorithm for approximating the number of q-colorings of an input graph with degree \Delta . Corollary 2 . There is an algorithm for approximating the number of q -colorings of a graph in \tilde{O}(\frac{n^{1/3}}{\epsilon^{2}}) rounds, when q>\alpha\Delta , for \alpha>2 , within multiplicative error \epsilon , with probability at least \frac{3}{4} . In the special case of the hardcore model,