In 1970, Hajnal and Szemerédi proved a conjecture of Erdős stating that any graph with maximum degree Δ admits an equitable (Δ+1)-coloring, that is, a coloring where color class sizes differ by at most 1. In 2007 Kierstead and Kostochka reproved their result and provided a polynomial-time algorithm which produces such a coloring. In this paper we study the problem of approximately sampling uniformly random equitable colorings. A series of works gives polynomial-time sampling algorithms for colorings without the color class constraint, the latest improvement being by Carlson and Vigoda for q ≥ 1.809 Δ. In this paper we give a polynomial-time sampling algorithm for equitable colorings when q > 2Δ. Moreover, our results extend to colorings with small deviations from equitable (and as a corollary, establishing their existence). The proof uses the framework of the geometry of polynomials for multivariate polynomials, and as a consequence establishes a multivariate local Central Limit Theorem for color class sizes of uniform random colorings.

We prove a hardness of sampling result for the anti-ferromagnetic Ising model on random graphs of average degree d for large constant d, proving that when the normalized inverse temperature satisfies β > 1 (asymptotically corresponding to the condensation threshold), then w.h.p. over the random graph there is no stable sampling algorithm that can output a sample close in W₂ distance to the Gibbs measure. The results also apply to a fixed-magnetization version of the model, showing that there are no stable sampling algorithms for low but positive temperature max and min bisection distributions. These results show a gap in the tractability of search and sampling problems: while there are efficient algorithms to find near optimizers, stable sampling algorithms cannot access the Gibbs distribution concentrated on such solutions. Our techniques involve extensions of the interpolation technique relating behavior of the mean field Sherrington-Kirkpatrick model to behavior of Ising models on random graphs of average degree d for large d. While previous interpolation arguments compared the free energies of the two models, our argument compares the average energies and average overlaps in the two models.

We study the following combinatorial counting and sampling problems: can we sample from the Erdős-Rényi random graph$G(n,p)$conditioned on triangle-freeness? Can we approximate (either algorithmically or with a formula) the probability that$G(n,p)$is triangle-free? These are prototypical instances of forbidden substructure problems ubiquitous in combinatorics. The algorithmic questions are instances of approximate sampling and counting for a hypergraph hard-core model. Estimating the probability that$G(n,p)$has no triangles is a fundamental question in probabilistic combinatorics and one that has led to the development of many important tools in the field. Through the work of several authors, the asymnpotics of the logarithm of this probability are known if$p=o(n^{-1/2})$or if$p=\omega(n^{-1/2})$. The regime$p=\Theta(n^{-1/2})$is more mysterious, as this range witnesses a dramatic change in the the typical structural properties of$G(n,p)$conditioned on triangle-freeness. As we show, this change in structure has a profound impact on the performance of sampling algorithms. We give two different efficient sampling algorithms for this problem (and complementary approximate counting algorithms), one that is efficient when$p < c/\sqrt{n}$and one that is efficient when$p > C/\sqrt{n}$for constants$c, C > 0$. The latter algorithm involves a new approach for dealing with large defects in the setting of sampling from low-temperature spin models. Our algorithmic results can be used to give an asymptotic formula for the logarithm of the probability$G(n,p)$is triangle-free when$p < c/\sqrt{n}$. This algorithmic approach to large deviation problems in random graphs is very different than the known approaches in the suBCRitical regime$p=o(n^{-1/2})$(based on the Poisson paradigm) and in the supercritical regime$p=\omega(n^{-1/2})$(based on regularity lemmas or hypergraph containers); in fact, to the best of our knowledge, no asymptotic formula for the log probability in the regime$p=\Theta(n^{-1/2})$was even conjectured previously.

We consider the algorithmic problem of finding large balanced independent sets in sparse random bipartite graphs, and more generally the problem of finding independent sets with specified proportions of vertices on each side of the bipartition. In a bipartite graph it is trivial to find an independent set of density at least half (take one of the partition classes). In contrast, in a random bipartite graph of average degree d, the largest balanced independent sets (containing equal number of vertices from each class) are typically of density . Can we find such large balanced independent sets in these graphs efficiently? By utilizing the overlap gap property and the low-degree algorithmic framework, we prove that local and low- degree algorithms (even those that know the bipartition) cannot find balanced independent sets of density greater than for any ɛ > 0 fixed and d large but constant. This factor 2 statistical-computational gap between what exists and what local algorithms can achieve is analogous to the gap for finding large independent sets in (non-bipartite) random graphs. Our results therefor suggest that this gap is pervasive in many models, and that hard computational problems can lurk inside otherwise tractable ones. A particularly striking aspect of the gap in bipartite graphs is that the algorithm achieving the lower bound is extremely simple and can be implemented as a 1-local algorithm and a degree-1 polynomial (a linear function).

We give an efficient perfect sampling algorithm for weighted, connected induced subgraphs (or graphlets ) of rooted, bounded degree graphs. Our algorithm utilizes a vertex-percolation process with a carefully chosen rejection filter and works under a percolation subcriticality condition. We show that this condition is optimal in the sense that the task of (approximately) sampling weighted rooted graphlets becomes impossible in finite expected time for infinite graphs and intractable for finite graphs when the condition does not hold. We apply our sampling algorithm as a subroutine to give near linear-time perfect sampling algorithms for polymer models and weighted non-rooted graphlets in finite graphs, two widely studied yet very different problems. This new perfect sampling algorithm for polymer models gives improved sampling algorithms for spin systems at low temperatures on expander graphs and unbalanced bipartite graphs, among other applications.

We provide a perfect sampling algorithm for the hard-sphere model on subsets of $\mathbb{R}^d$ with expected running time linear in the volume under the assumption of strong spatial mixing. A large number of perfect and approximate sampling algorithms have been devised to sample from the hard-sphere model, and our perfect sampling algorithm is efficient for a range of parameters for which only efficient approximate samplers were previously known and is faster than these known approximate approaches. Our methods also extend to the more general setting of Gibbs point processes interacting via finite-range, repulsive potentials.

For many computational problems involving randomness, intricate geometric features of the solution space have been used to rigorously rule out powerful classes of algorithms. This is often accomplished through the lens of the multi Overlap Gap Property ($m$-OGP), a rigorous barrier against algorithms exhibiting input stability. In this paper, we focus on the algorithmic tractability of two models: (i) discrepancy minimization, and (ii) the symmetric binary perceptron (\texttt{SBP}), a random constraint satisfaction problem as well as a toy model of a single-layer neural network.Our first focus is on the limits of online algorithms. By establishing and leveraging a novel geometrical barrier, we obtain sharp hardness guarantees against online algorithms for both the \texttt{SBP} and discrepancy minimization. Our results match the best known algorithmic guarantees, up to constant factors. Our second focus is on efficiently finding a constant discrepancy solution, given a random matrix $\mathcal{M}\in\R^{M\times n}$. In a smooth setting, where the entries of $\mathcal{M}$ are i.i.d.\,standard normal, we establish the presence of $m$-OGP for $n=\Theta(M\log M)$. Consequently, we rule out the class of stable algorithms at this value. These results give the first rigorous evidence towards \citet[Conjecture 1]{altschuler2021discrepancy}. Our methods use the intricate geometry of the solution space to prove tight hardness results for online algorithms. The barrier we establish is a novel variant of the $m$-OGP. Furthermore, it regards $m$-tuples of solutions with respect to correlated instances, with growing values of $m$, $m=\omega(1)$. Importantly, our results rule out online algorithms succeeding even with an exponentially small probability.

Abstract. We determine the computational complexity of approximately counting and sampling independent sets of a given size in bounded-degree graphs. That is, we identify a critical density [Formula: see text] and provide (i) for [Formula: see text] randomized polynomial-time algorithms for approximately sampling and counting independent sets of given size at most [Formula: see text] in [Formula: see text]-vertex graphs of maximum degree [Formula: see text], and (ii) a proof that unless NP = RP, no such algorithms exist for [Formula: see text]. The critical density is the occupancy fraction of the hard-core model on the complete graph [Formula: see text] at the uniqueness threshold on the infinite [Formula: see text]-regular tree, giving [Formula: see text] as [Formula: see text]. Our methods apply more generally to antiferromagnetic 2-spin systems and motivate new questions in extremal combinatorics.

Abstract. Approximating the partition function of the ferromagnetic Ising model with general external fields is known to be #BIS-hard in the worst case, even for bounded-degree graphs, and it is widely believed that no polynomial-time approximation scheme exists. This motivates an average-case question: are there classes of instances for which polynomial-time approximation schemes exist? We investigate this question for the random field Ising model on graphs with maximum degree [Formula: see text]. We establish the existence of fully polynomial-time approximation schemes and samplers with high probability over the random fields if the external fields are independent and identically distributed Gaussians with variance larger than a constant depending only on the inverse temperature and [Formula: see text]. Our methods work more generally for external fields that are large in absolute value with high probability. The main challenge is that such a hypothesis does not rule out the existence of a positive density of vertices at which the external field is small. These regions, which may have connected components of size [Formula: see text], are a barrier to algorithms based on establishing zero-free regions of partition functions and cause worst-case analyses of Glauber dynamics to fail. The analysis of our algorithm is based on percolation on a self-avoiding walk tree.

We give an efficient perfect sampling algorithm for weighted, connected induced subgraphs (or graphlets) of rooted, bounded degree graphs. Our algorithm utilizes a vertex-percolation process with a carefully chosen rejection filter and works under a percolation subcriticality condition. We show that this condition is optimal in the sense that the task of (approximately) sampling weighted rooted graphlets becomes impossible in finite expected time for infinite graphs and intractable for finite graphs when the condition does not hold. We apply our sampling algorithm as a subroutine to give near linear-time perfect sampling algorithms for polymer models and weighted non-rooted graphlets in finite graphs, two widely studied yet very different problems. This new perfect sampling algorithm for polymer models gives improved sampling algorithms for spin systems at low temperatures on expander graphs and unbalanced bipartite graphs, among other applications.

The binary (or Ising) perceptron is a toy model of a single-layer neural network and can be viewed as a random constraint satisfaction problem with a high degree of connectivity. The model and its symmetric variant, the symmetric binary perceptron (SBP), have been studied widely in statistical physics, mathematics, and machine learning.The SBP exhibits a dramatic statistical-to-computational gap: the densities at which known efficient algorithms find solutions are far below the threshold for the existence of solutions. Furthermore, the SBP exhibits a striking structural property: at all positive constraint densities almost all of its solutions are ‘totally frozen’ singletons separated by large Hamming distance [1], [2]. This suggests that finding a solution to the SBP may be computationally intractable. At the same time, however, the SBP does admit polynomial-time search algorithms at low enough densities. A conjectural explanation for this conundrum was put forth in [3]: efficient algorithms succeed in the face of freezing by finding exponentially rare clusters of large size. However, it was discovered recently that such rare large clusters exist at all subcritical densities, even at those well above the limits of known efficient algorithms [4]. Thus the driver of the statistical-to-computational gap exhibited by this model remains a mystery. In this paper, we conduct a different landscape analysis to explain the statistical-to-computational gap exhibited by this problem. We show that at high enough densities the SBP exhibits the multi Overlap Gap Property (m-OGP), an intricate geometrical property known to be a rigorous barrier for large classes of algorithms. Our analysis shows that the m-OGP threshold (a) is well below the satisfiability threshold; and (b) matches the best known algorithmic threshold up to logarithmic factors as $m\rightarrow\infty$. We then prove that the m-OGP rules out the class of stable algorithms for the SBP above this threshold. We conjecture that the $m\rightarrow\infty$ limit of the m-OGP threshold marks the algorithmic threshold for the problem. Furthermore, we investigate the stability of known efficient algorithms for perceptron models and show that the Kim-Roche algorithm [5], devised for the asymmetric binary perceptron, is stable in the sense we consider.

By implementing algorithmic versions of Sapozhenko's graph container methods, we give new algorithms for approximating the number of independent sets in bipartite graphs. The first algorithm applies to d-regular, bipartite graphs satisfying a weak expansion condition: when d is constant, and the graph is a Ω(log2 d/d)-bipartite expander, we obtain an FPTAS for the number of independent sets. Previously such a result for d > 5 was known only for graphs satisfying the much stronger expansion conditions of random graphs. The second algorithm applies to all d-regular, bipartite graphs, runs in time exp , and outputs a (1 + o(1))-approximation to the number of independent sets.

The ferromagnetic Ising model is a model of a magnetic material and a central topic in statistical physics. It also plays a starring role in the algorithmic study of approximate counting: approximating the partition function of the ferromagnetic Ising model with uniform external field is tractable at all temperatures and on all graphs, due to the randomized algorithm of Jerrum and Sinclair.

We give an FPTAS for computing the number of matchings of size k in a graph G of maximum degree Δ on n vertices, for all k ≤ (1−δ)m*(G), where δ>0 is fixed and m*(G) is the matching number of G, and an FPTAS for the number of independent sets of size k ≤ (1−δ) αc(Δ) n, where αc(Δ) is the NP-hardness threshold for this problem. We also provide quasi-linear time randomized algorithms to approximately sample from the uniform distribution on matchings of size k ≤ (1−δ)m*(G) and independent sets of size k ≤ (1−δ)αc(Δ)n.

We determine the computational complexity of approximately counting and sampling independent sets of a given size in bounded-degree graphs. That is, we identify a critical density α_c(Δ) and provide (i) for α < α_c(Δ) randomized polynomial-time algorithms for approximately sampling and counting independent sets of given size at most α n in n-vertex graphs of maximum degree Δ; and (ii) a proof that unless NP=RP, no such algorithms exist for α > α_c(Δ). The critical density is the occupancy fraction of hard core model on the clique K_{Δ+1} at the uniqueness threshold on the infinite Δ-regular tree, giving α_c(Δ) ~ e/(1+e)1/(Δ) as Δ → ∞.

We prove, under an assumption on the critical points of a real-valued function, that the symmetric Ising perceptron exhibits the `frozen 1-RSB' structure conjectured by Krauth and Mezard in the physics literature; that is, typical solutions of the model lie in clusters of vanishing entropy density. Moreover, we prove this in a very strong form conjectured by Huang, Wong, and Kabashima: a typical solution of the model is isolated with high probability and the Hamming distance to all other solutions is linear in the dimension. The frozen 1-RSB scenario is part of a recent and intriguing explanation of the performance of learning algorithms by Baldassi, Ingrosso, Lucibello, Saglietti, and Zecchina. We prove this structural result by comparing the symmetric Ising perceptron model to a planted model and proving a comparison result between the two models. Our main technical tool towards this comparison is an inductive argument for the concentration of the logarithm of number of solutions in the model.

Understanding the complexity of approximately counting the number of weighted or unweighted independent sets in a bipartite graph (#BIS) is a central open problem in the field of approximate counting. Here we consider a subclass of this problem and give an FPTAS for approximating the partition function of the hard-core model for bipartite graphs when there is sufficient imbalance in the degrees or fugacities between the sides (L, R) of the bipartition. This includes, among others, the biregular case when λ = 1 (approximating the number of independent sets of G) and ΔR ≥ 7ΔL log(ΔL). Our approximation algorithm is based on truncating the cluster expansion of a polymer model partition function that expresses the hard-core partition function in terms of deviations from independent sets that are empty on one side of the bipartition. Further consequences of this method for unbalanced bipartite graphs include an efficient sampling algorithm for the hard-core model and zero-freeness results for the partition function with complex fugacities. By utilizing connections between the cluster expansion and joint cumulants of certain random variables, we go beyond previous algorithmic applications of the cluster expansion to prove that the hard-core model exhibits exponential decay of correlations for all graphs and fugacities satisfying our conditions. This illustrates the applicability of statistical mechanics tools to algorithmic problems and refines our understanding of the connections between different methods of approximate counting.

For d ≥ 2 and all q≥ q 0(d) we give an efficient algorithm to approximately sample from the q-state ferromagnetic Potts and random cluster models on the torus (ℤ / n ℤ ) d for any inverse temperature β≥ 0. This stands in contrast to Markov chain mixing time results: the Glauber dynamics mix slowly at and below the critical temperature, and the Swendsen–Wang dynamics mix slowly at the critical temperature. We also provide an efficient algorithm (an FPRAS) for approximating the partition functions of these models.

We give a fully polynomial-time approximation scheme (FPTAS) and an efficient sampling algorithm for the high-fugacity hard-core model on bounded-degree bipartite expander graphs and the low-temperature ferromagnetic Potts model on bounded-degree expander graphs. The results apply, for example, to random (bipartite) $\Delta$-regular graphs, for which no efficient algorithms were known for these problems (with the exception of the Ising model) in the nonuniqueness regime of the infinite $\Delta$-regular tree. We also find efficient counting and sampling algorithms for proper $q$-colorings of random $\Delta$-regular bipartite graphs when $q$ is sufficiently small as a function of $\Delta$.

For spin systems, such as the hard-core model on independent sets weighted by fugacity lambda>0, efficient algorithms for the associated approximate counting/sampling problems typically apply in the high-temperature region, corresponding to low fugacity. Recent work of Jenssen, Keevash and Perkins (2019) yields an FPTAS for approximating the partition function (and an efficient sampling algorithm) on bounded-degree (bipartite) expander graphs for the hard-core model at sufficiently high fugacity, and also the ferromagnetic Potts model at sufficiently low temperatures. Their method is based on using the cluster expansion to obtain a complex zero-free region for the partition function of a polymer model, and then approximating this partition function using the polynomial interpolation method of Barvinok. We present a simple discrete-time Markov chain for abstract polymer models, and present an elementary proof of rapid mixing of this new chain under sufficient decay of the polymer weights. Applying these general polymer results to the hard-core and ferromagnetic Potts models on bounded-degree (bipartite) expander graphs yields fast algorithms with running time O(n log n) for the Potts model and O(n^2 log n) for the hard-core model, in contrast to typical running times of n^{O(log Delta)} for algorithms based on Barvinok’s polynomial interpolation method on graphs of maximum degree Delta. In addition, our approach via our polymer model Markov chain is conceptually simpler as it circumvents the zero-free analysis and the generalization to complex parameters. Finally, we combine our results for the hard-core and ferromagnetic Potts models with standard Markov chain comparison tools to obtain polynomial mixing time for the usual spin system Glauber dynamics restricted to even and odd or "red" dominant portions of the respective state spaces.

We give an FPTAS and an efficient sampling algorithm for the high-fugacity hard-core model on bounded-degree bipartite expander graphs and the low-temperature ferromagnetic Potts model on bounded-degree expander graphs. The results apply, for example, to random (bipartite) Δ-regular graphs, for which no efficient algorithms were known for these problems (with the exception of the Ising model) in the non-uniqueness regime of the infinite Δ-regular tree.

The problem of identifying a planted assignment given a random $k$-satisfiability ($k$-SAT) formula consistent with the assignment exhibits a large algorithmic gap: while the planted solution becomes unique and can be identified given a formula with $O(n\log n)$ clauses, there are distributions over clauses for which the best-known efficient algorithms require $n^{k/2}$ clauses. We propose and study a unified model for planted $k$-SAT, which captures well-known special cases. An instance is described by a planted assignment $\sigma$ and a distribution on clauses with $k$ literals. We define its distribution complexity as the largest $r$ for which the distribution is not $r$-wise independent ($1 \le r \le k$ for any distribution with a planted assignment). Our main result is an unconditional lower bound, tight up to logarithmic factors, for statistical (query) algorithms [M. Kearns, J. ACM, 45 (1998), pp. 983--1006; V. Feldman, E. Grigorescu, L. Reyzin, S. S. Vempala, and Y. Xiao, J. ACM, 64 (2017), pp. 8:1--8:37], matching known upper bounds, which, as we show, can be implemented using a statistical algorithm. Since known approaches for problems over distributions have statistical analogues (spectral, Markov Chain Monte Carlo, gradient-based, convex optimization, etc.), this lower bound provides a rigorous explanation of the observed algorithmic gap. The proof introduces a new general technique for the analysis of statistical query algorithms. It also points to a geometric paring phenomenon in the space of all planted assignments. We describe consequences of our lower bounds to Feige's refutation hypothesis [U. Feige, Proceedings of the ACM Symposium on Theory of Computing, 2002, pp. 534--543] and to lower bounds on general convex programs that solve planted $k$-SAT. Our bounds also extend to other planted $k$-CSP models and, in particular, provide concrete evidence for the security of Goldreich's one-way function and the associated pseudorandom generator when used with a sufficiently hard predicate [O. Goldreich, preprint, ia.cr/2000/063, 2000].

Vindicating a sophisticated but non-rigorous physics approach called the cavity method, we establish a formula for the mutual information in statistical inference problems induced by random graphs. This general result implies the conjecture on the information-theoretic threshold in the disassortative stochastic block model [Decelle et al.: Phys. Rev. E (2011)] and allows us to pinpoint the exact condensation phase transition in random constraint satisfaction problems such as random graph coloring, thereby proving a conjecture from [Krzakala et al.: PNAS (2007)]. As a further application we establish the formula for the mutual information in Low-Density Generator Matrix codes as conjectured in [Montanari: IEEE Transactions on Information Theory (2005)]. The proofs provide a conceptual underpinning of the replica symmetric variant of the cavity method, and we expect that the approach will find many future applications.

We consider a bipartite stochastic block model on vertex sets V_1 and V_2, with planted partitions in each, and ask at what densities efficient algorithms can recover the partition of the smaller vertex set. When |V_2| ≫|V_1|, multiple thresholds emerge. We first locate a sharp threshold for detection of the partition, in the sense of the results of Mossel, Neeman and Sly and Massoulie for the stochastic block model. We then show that at a higher edge density, the singular vectors of the rectangular biadjacency matrix exhibit a localization / delocalization phase transition, giving recovery above the threshold and no recovery below. Nevertheless, we propose a simple spectral algorithm, Diagonal Deletion SVD, which recovers the partition at a nearly optimal edge density. The bipartite stochastic block model studied here was used by Feldman, Perkins, Vempala to give a unified algorithm for recovering planted partitions and assignments in random hypergraphs and random k-SAT formulae respectively. Our results give the best known bounds for the clause density at which solutions can be found efficiently in these models as well as showing a barrier to further improvement via this reduction to the bipartite block model.

We present an algorithm for recovering planted solutions in two well-known models, the stochastic block model and planted constraint satisfaction problems (CSP), via a common generalization in terms of random bipartite graphs. Our algorithm matches up to a constant factor the best-known bounds for the number of edges (or constraints) needed for perfect recovery and its running time is linear in the number of edges used. The time complexity is significantly better than both spectral and SDP-based approaches.The main contribution of the algorithm is in the case of unequal sizes in the bipartition that arises in our reduction from the planted CSP. Here our algorithm succeeds at a significantly lower density than the spectral approaches, surpassing a barrier based on the spectral norm of a random matrix.Other significant features of the algorithm and analysis include (i) the critical use of power iteration with subsampling, which might be of independent interest; its analysis requires keeping track of multiple norms of an evolving solution (ii) the algorithm can be implemented statistically, i.e., with very limited access to the input distribution (iii) the algorithm is extremely simple to implement and runs in linear time, and thus is practical even for very large instances.

The problem of identifying a planted assignment given a random k-SAT formula consistent with the assignment exhibits a large algorithmic gap: while the planted solution can always be identified given a formula with O(n log n) clauses, there are distributions over clauses for which the best known efficient algorithms require nk/2 clauses. We propose and study a unified model for planted k-SAT, which captures well-known special cases. An instance is described by a planted assignment σ and a distribution on clauses with k literals. We define its distribution complexity as the largest r for which the distribution is not r-wise independent (1 ≤ r ≤ k for any distribution with a planted assignment).

We give a characterization of vertex-monotone properties with sharp thresholds in a Poisson random geometric graph or hypergraph. As an application we show that a geometric model of random k-SAT exhibits a sharp threshold for satisfiability.

For every ∈ > 0, and integer q ≥ 3, we show that given an N-vertex graph that has an induced q-colorable subgraph of size (1 - ∈)N, it is NP-hard to find an independent set of size N/q2.