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.

For positive integersn, r, swithr>s, the setcoloring Ramsey numberR(n; r, s) is the minimumNsuch that if every edge of the complete graphKNreceives a set ofscolors from a palette ofrcolors, then there is a subset ofnvertices where all of the edges between them receive a common color. Ifnis fixed ands/ris less than and bounded away from 1 - 1/n-1, thenR(n; r, s) is known to grow exponentially in r, while ifs/ris greater than and bounded away from 1 - 1/n-1, thenR(n; r, s) is bounded. Here we prove bounds forR(n; r, s) in the intermediate range wheres/ris close to 1 - 1/n-1 by establishing a connection to the maximum size of error-correcting codes near the zero-rate threshold.

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.

Proving the “expectation-threshold” conjecture of Kahn and Kalai, we show that for any increasing property $\mathcal{F}$ on a finite set X,\begin{equation*}p_{c}(\mathcal{F})=O(q(\mathcal{F})\log\ell(\mathcal{F})),\end{equation*}where $p_{c}(\mathcal{F})$ and $q(\mathcal{F})$ are the threshold and “expectation threshold” of $\mathcal{F}$, and $\ell(\mathcal{F})$ is the maximum size of a minimal member of $\mathcal{F}$.

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.

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

The mean field theory of multilayer neural networks centers around a particular infinite-width scaling, in which the learning dynamics is shown to be closely tracked by the mean field limit. A random fluctuation around this infinite-width limit is expected from a large-width expansion to the next order. This fluctuation has been studied only in the case of shallow networks, where previous works employ heavily technical notions or additional formulation ideas amenable only to that case. Treatment of the multilayer case has been missing, with the chief difficulty in finding a formulation that must capture the stochastic dependency across not only time but also depth.In this work, we initiate the study of the fluctuation in the case of multilayer networks, at any network depth. Leveraging on the neuronal embedding framework recently introduced by Nguyen and Pham, we systematically derive a system of dynamical equations, called the second-order mean field limit, that captures the limiting fluctuation distribution. We demonstrate through the framework the complex interaction among neurons in this second-order mean field limit, the stochasticity with cross-layer dependency and the nonlinear time evolution inherent in the limiting fluctuation. A limit theorem is proven to relate quantitatively this limit to the fluctuation realized by large-width networks.We apply the result to show a stability property of gradient descent mean field training: in the large-width regime, along the training trajectory, it progressively biases towards a solution with "minimal fluctuation" (in fact, vanishing fluctuation) in the learned output function, even after the network has been initialized at or has converged (sufficiently fast) to a global optimum. This extends a similar phenomenon previously shown only for shallow networks with a squared loss in the empirical risk minimization setting, to multilayer networks with a loss function that is not necessarily convex in a more general setting.