Let G = (V,E) be a graph on n vertices and let m^*(G) denote the size of a maximum matching in G. We show that for any δ > 0 and for any 1 ≤ k ≤ (1-δ)m^*(G), the down-up walk on matchings of size k in G mixes in time polynomial in n. Previously, polynomial mixing was not known even for graphs with maximum degree Δ, and our result makes progress on a conjecture of Jain, Perkins, Sah, and Sawhney [STOC, 2022] that the down-up walk mixes in optimal time O_{Δ,δ}(nlog{n}). In contrast with recent works analyzing mixing of down-up walks in various settings using the spectral independence framework, we bound the spectral gap by constructing and analyzing a suitable multi-commodity flow. In fact, we present constructions demonstrating the limitations of the spectral independence approach in our setting.

We study Glauber dynamics for sampling from discrete distributions μ on the hypercube {±1}n. Recently, techniques based on spectral independence have successfully yielded optimal O(n) relaxation times for a host of different distributions μ. We show that spectral independence is universal: a relaxation time of O(n) implies spectral independence.

Given a graph G, a random (k, n)-list assignment L for edges of G is an assignment of an independent, uniformly random set of colors to each edge e and a proper L-list coloring of G is a proper edge-coloring where the color of an edge e belongs to L(e). We show that for a random (O(log n), n)-list assignment L for edges of the complete bipartite graph Kn,n, there is a an L-list coloring of Kn,n with high probability. We also prove analogous results for the thresholds of Steiner triple systems and Latin squares in random (binomial) hypergraphs. All of our results are optimal up to absolute constants, and resolve several related conjectures of Johansson, Luria-Simkin, Casselgren-Häggkvist, Simkin, and Kang-Kelly-Kühn-Methuku-Osthus.

Let G be a graph on n vertices of maximum degree $\Delta$. We show that, for any $\delta\gt0$, the down-up walk on independent sets of size $k \leq(1-\delta) \alpha_{c}(\Delta) n$ mixes in time $O_{\Delta, \delta}(k \log n)$, thereby resolving a conjecture of Davies and Perkins in an optimal form. Here, $\alpha_{c}(\Delta) n$ is the NP-hardness threshold for the problem of counting independent sets of a given size in a graph on n vertices of maximum degree $\Delta$. Our mixing time has optimal dependence on $k, n$ for the entire range of k; previously, even polynomial mixing was not known. In fact, for $k=\Omega_{\Delta}(n)$ in this range, we establish a log-Sobolev inequality with optimal constant $\Omega_{\Delta, \delta}(1 / n)$.At the heart of our proof are three new ingredients, which may be of independent interest. The first is a method for lifting $\ell_{\infty}$-independence from a suitable distribution on the discrete cube—in this case, the hard-core model—to the slice by proving stability of an Edgeworth expansion using a multivariate zero-free region for the base distribution. The second is a generalization of the Lee-Yau induction to prove log-Sobolev inequalities for distributions on the slice with considerably less symmetry than the uniform distribution. The third is a sharp decomposition-type result which provides a lossless comparison between the Dirichlet form of the original Markov chain and that of the so-called projected chain in the presence of a contractive coupling.

A celebrated theorem of Spencer states that for every set system S1,…, Sm ⊆ [n], there is a coloring of the ground set with {±1} with discrepancy . We provide an algorithm to find such a coloring in near input-sparsity time Õ(n + Σi=1m|Si|)

Let$X$be a random vector valued in$\mathbb {R}^{m}$such that$\|X\|_{2} \le 1$almost surely. For every$k\ge 3$, we show that there exists a sigma algebra$\mathcal {F}$generated by a partition of$\mathbb {R}^{m}$into$k$sets such that$\|\mathrm {Cov}(X) - \mathrm {Cov}(\mathbb {E}[X\mid \mathcal {F}]) \|_{\mathrm {F}} \lesssim \frac {1}{\sqrt {\log {k}}}$. This is optimal up to the implicit constant and improves on a previous bound due to Boedihardjo, Strohmer, and Vershynin. Our proof provides an efficient algorithm for constructing$\mathcal {F}$and leads to improved accuracy guarantees for$k$-anonymous or differentially private synthetic data. We also establish a connection between the above problem of minimizing the covariance loss and the pinning lemma from statistical physics, providing an alternate (and much simpler) algorithmic proof in the important case when$X \in \{\pm 1\}^{m}/\sqrt {m}$almost surely.

We introduce a notion called entropic independence that is an entropic analog of spectral notions of high-dimensional expansion. Informally, entropic independence of a background distribution µ on k-sized subsets of a ground set of elements says that for any (possibly randomly chosen) set S, the relative entropy of a single element of S drawn uniformly at random carries at most O(1/k) fraction of the relative entropy of S. Entropic independence is the analog of the notion of spectral independence, if one replaces variance by entropy. We use entropic independence to derive tight mixing time bounds, overcoming the lossy nature of spectral analysis of Markov chains on exponential-sized state spaces.

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.

Let$\Phi=(V, \mathcal{C})$be a constraint satisfaction problem on variables$v_{1}, \ldots, v_{n}$such that each constraint depends on at most$k$variables and such that each variable assumes values in an alphabet of size at most [$q$]. Suppose that each constraint shares variables with at most$\Delta$constraints and that each constraint is violated with probability at most$p$(under the product measure on its variables). We show that for$k, q=O(1)$, there is a deterministic, polynomial time algorithm to approximately count the number of satisfying assignments and a randomized, polynomial time algorithm to sample from approximately the uniform distribution on satisfying assignments, provided that$C\cdot q^{2}\cdot k\cdot p\cdot\Delta^{7} < 1$, where$C$is an absolute constant. Previously, a result of this form was known essentially only in the special case when each constraint is violated by exactly one assignment to its variables. For the special case of$k$.CNF formulas, the term$\Delta^{7}$improves the previously best known$\Delta^{60}$for deterministic algorithms [Moitra, J.ACM, 2019] and$\Delta^{13}$for randomized algorithms [Feng, Guo, Yin, and Zhang, STOC 2021]. For the special case of properly$q$-coloring$k$-uniform hypergraphs, the term$\Delta^{7}$improves the previously best known$\Delta^{14}$for deterministic algorithms [Guo, Liao, Lu, and Zhang, SICOMP, 2019] and$\Delta^{9}$for randomized algorithms [Feng, Guo, Yin, and Zhang, STOC 2021].

We present a randomized algorithm which takes as input an undirected graph G on n vertices with maximum degree Δ, and a number of colors k ≥ (8/3 + oΔ(1))Δ, and returns – in expected time Õ(nΔ2logk) – a proper k-coloring of G distributed perfectly uniformly on the set of all proper k-colorings of G. Notably, our sampler breaks the barrier at k = 3Δ encountered in recent work of Bhandari and Chakraborty [STOC 2020]. We also discuss how our methods may be modified to relax the restriction on k to k ≥ (8/3 − є0)Δ for an absolute constant є0 > 0.

The analysis of Belief Propagation and other algorithms for the {\em reconstruction problem} plays a key role in the analysis of community detection in inference on graphs, phylogenetic reconstruction in bioinformatics, and the cavity method in statistical physics. We prove a conjecture of Evans, Kenyon, Peres, and Schulman (2000) which states that any bounded memory message passing algorithm is statistically much weaker than Belief Propagation for the reconstruction problem. More formally, any recursive algorithm with bounded memory for the reconstruction problem on the trees with the binary symmetric channel has a phase transition strictly below the Belief Propagation threshold, also known as the Kesten-Stigum bound. The proof combines in novel fashion tools from recursive reconstruction, information theory, and optimal transport, and also establishes an asymptotic normality result for BP and other message-passing algorithms near the critical threshold.

The free energy is a key quantity of interest in Ising models, but unfortunately, computing it in general is computationally intractable. Two popular (variational) approximation schemes for estimating the free energy of general Ising models (in particular, even in regimes where correlation decay does not hold) are: (i) the mean-field approximation with roots in statistical physics, which estimates the free energy from below, and (ii) hierarchies of convex relaxations with roots in theoretical computer science, which estimate the free energy from above. We show, surprisingly, that the tight regime for both methods to compute the free energy to leading order is identical.

The mean field approximation to the Ising model is a canonical variational tool that is used for analysis and inference in Ising models. We provide a simple and optimal bound for the KL error of the mean field approximation for Ising models on general graphs, and extend it to higher order Markov random fields. Our bound improves on previous bounds obtained in work in the graph limit literature by Borgs, Chayes, Lov{á}sz, S{ó}s, and Vesztergombi and recent works by Basak and Mukherjee, and Eldan. Our bound is tight up to lower order terms. Building on the methods used to prove the bound, along with techniques from combinatorics and optimization, we study the algorithmic problem of estimating the (variational) free energy for Ising models and general Markov random fields. For a graph $G$ on $n$ vertices and interaction matrix $J$ with Frobenius norm $\|{J} \|_F$, we provide algorithms that approximate the free energy within an additive error of $\epsilon n \|J\|_F$ in time $\exp(poly(1/\epsilon))$. We also show that approximation within $(n \|J\|_F)^{1-\delta}$ is NP-hard for every $\delta > 0$. Finally, we provide more efficient approximation algorithms, which find the optimal mean field approximation, for ferromagnetic Ising models and for Ising models satisfying Dobrushin’s condition.

The free energy is a key quantity which is associated to Markov random fields. Classical results in statistical physics show how, given an analytic formula of the free energy, it is possible to compute many key quantities associated with Markov random fields including quantities such as magnetization and the location of various phase transitions. Given a massive Markov random field on $n$ nodes, can a small sample from it provide a rough approximation to the free energy $\mathcal{F}_n = \log{Z_n}$? Results in the graph limit literature by Borgs, Chayes, Lov{á}sz, S{ó}s, and Vesztergombi show that for Ising models on $n$ nodes and interactions of strength $\Theta(1/n)$, an $\epsilon$ approximation to $\log Z_n / n$ can be achieved by sampling a randomly induced model on $2^{O(1/\epsilon^2)}$ nodes. We show that the sampling complexity of this problem is {\em polynomial in }$1/\epsilon$. We further show a polynomial dependence on $\epsilon$ cannot be avoided. Our results are very general as they apply to higher order Markov random fields. For Markov random fields of order $r$, we obtain an algorithm that achieves $\epsilon$ approximation using a number of samples polynomial in $r$ and $1/\epsilon$ and running time that is $2^{O(1/\epsilon^2)}$ up to polynomial factors in $r$ and $\epsilon$. For ferromagnetic Ising models, the running time is polynomial in $1/\epsilon$. Our results are intimately connected to recent research on the regularity lemma and property testing, where the interest is in finding which properties can tested within $\epsilon$ error in time polynomial in $1/\epsilon$. In particular, our proofs build on results of Alon, de la Vega, Kannan and Karpinski, who also introduced the notion of polynomial vertex sample complexity. Another critical ingredient of the proof is an effective bound by the authors of this paper relating the variational free energy and the free energy.