We present a sublinear time algorithm that gives random local access to the uniform distribution over satisfying assignments to an arbitrary k-SAT formula Φ, at exponential clause density. Our algorithm provides memory-less query access to variable assignments, such that the output variable assignments consistently emulate a single global satisfying assignment whose law is close to the uniform distribution over satisfying assignments to Φ. Random local access and related models have been studied for a wide variety of natural Gibbs distributions and random graphical processes. Here, we establish feasibility of random local access models for one of the most canonical such sample spaces, the set of satisfying assignments to a k-SAT formula. Our algorithm proceeds by leveraging the local uniformity of the uniform distribution over satisfying assignments to Φ. We randomly partition the variables into two subsets, so that each clause has sufficiently many variables from each set to preserve local uniformity. We then sample some variables by simulating a systematic scan Glauber dynamics backward in time, greedily constructing the necessary intermediate steps. We sample the other variables by first conducting a search for a polylogarithmic-sized local component, which we iteratively grow to identify a small subformula from which we can efficiently sample using the appropriate marginal distribution. This two-pronged approach enables us to sample individual variable assignments without constructing a full solution.

Abstract. We give a nearly linear-time algorithm to approximately sample satisfying assignments in the random [Formula: see text]-SAT model when the density of the formula scales exponentially with [Formula: see text]. The best previously known sampling algorithm for the random [Formula: see text]-SAT model applies when the density [Formula: see text] of the formula is less than [Formula: see text] and runs in time [Formula: see text] [Galanis et al., SIAM J. Comput., 50 (2021), pp. 1701–1738]. Here [Formula: see text] is the number of variables and [Formula: see text] is the number of clauses. Our algorithm achieves a significantly faster running time of [Formula: see text] and samples satisfying assignments up to density [Formula: see text]. The main challenge in our setting is the presence of many variables with unbounded degree, which causes significant correlations within the formula and impedes the application of relevant Markov chain methods from the bounded-degree setting [Feng et al., J. ACM, 68 (2021) 40; Jain, Pham, and Vuong, On the Sampling Lovász Local Lemma for Atomic Constraint Satisfaction Problems, 2021]. Our main technical contribution is a [Formula: see text] bound of the sum of influences in the [Formula: see text]-SAT model which turns out to be robust against the presence of high-degree variables. This allows us to apply the spectral independence framework and obtain fast mixing results of a uniform-block Glauber dynamics on a carefully selected subset of the variables. The final key ingredient in our method is to take advantage of the sparsity of logarithmic-sized connected sets and the expansion properties of the random formula, and establish relevant connectivity properties of the set of satisfying assignments that enable the fast simulation of this Glauber dynamics. Our results also allow us to conclude that, with high probability, a random [Formula: see text]-CNF formula with density at most [Formula: see text] has a giant component of solutions that are connected in a graph where solutions are adjacent if they have Hamming distance [Formula: see text]. We are also able to deduce looseness results for random [Formula: see text]-CNFs in the same regime.

Strong spatial mixing (SSM) is an important quantitative notion of correlation decay for Gibbs distributions arising in statistical physics, probability theory, and theoretical computer science. A longstanding conjecture is that the uniform distribution on proper q-colorings on a $\Delta$ regular tree exhibits SSM whenever $q \geq \Delta+1$. Moreover, it is widely believed that as long as SSM holds on bounded-degree trees with q colors, one would obtain an efficient sampler for q-colorings on all bounded-degree graphs via simple Markov chain algorithms. It is surprising that such a basic question is still open, even on trees, but then again it also highlights how much we still have to learn about random colorings. In this paper, we show the following: (1)For any $\Delta \geq 3$, SSM holds for random q-colorings on trees of maximum degree $\Delta$ whenever $q \geq \Delta+3$. Thus we almost fully resolve the aforementioned conjecture. Our result substantially improves upon the previously best bound which requires $q \geq 1.59 \Delta+\gamma^{*}$ for an absolute constant $\gamma^{*}\gt0$.(2)For any $\Delta \geq 3$ and $g=\Omega_{\Delta}(1)$, we establish optimal mixing of the Glauber dynamics for q-colorings on graphs of maximum degree $\Delta$ and girth g whenever $q \geq \Delta+3$. Our approach is based on a new general reduction from spectral independence on large-girth graphs to SSM on trees that is of independent interest. Using the same techniques, we also prove near-optimal bounds on weak spatial mixing (WSM), a closely-related notion to SSM, for the antiferromagnetic Potts model on trees.

We take an algorithmic approach to studying the solution space geometry of relatively sparse random and bounded degree k-CNFs for large k. In the course of doing so, we establish that with high probability, a random k-CNF Φ with n variables and clause density α = m/n ≲ 2k/6 has a giant component of solutions that are connected in a graph where solutions are adjacent if they have Hamming distance Ok(log n) and that a similar result holds for bounded degree k-CNFs at similar densities. We are also able to deduce looseness results for random and bounded degree k-CNFs in a similar regime. Although our main motivation was understanding the geometry of the solution space, our methods have algorithmic implications. Towards that end, we construct an idealized block dynamics that samples solutions from a random k-CNF Φ with density α = m/n ≲ 2k/52. We show this Markov chain can with high probability be implemented in polynomial time and by leveraging spectral independence, we also observe that it mixes relatively fast, giving a polynomial time algorithm to with high probability sample a uniformly random solution to a random k-CNF. Our work suggests that the natural route to pinning down when a giant component exists is to develop sharper algorithms for sampling solutions to random k-CNFs.

We prove that 1−o(1) fraction of all k-SAT functions on n Boolean variables are unate (i.e., monotone after first negating some variables), for any fixed positive integer k and as n → ∞. This resolves a conjecture by Bollobás, Brightwell, and Leader from 2003.

How many k-SAT functions on n boolean variables are there? What does a typical such function look like? Bollobás, Brightwell, and Leader conjectured that, for each fixed k ≥ 2, the number of k-SAT functions on n variables is , or equivalently: a 1–o(1) fraction of all k-SAT functions are unate, i.e., monotone after negating some variables. They proved a weaker version of the conjecture for k = 2. The conjecture was confirmed for k = 2 by Allen and k = 3 by Ilinca and Kahn. We show that the problem of enumerating k-SAT functions is equivalent to a Turán density problem for partially directed hypergraphs. Our proof uses the hypergraph container method. Furthermore, we confirm the Bollobás–Brightwell–Leader conjecture for k = 4 by solving the corresponding Turán density problem.

Hateful memes are an emerging method of spreading hate on the internet, relying on both images and text to convey a hateful message. We take an interpretable approach to hateful meme detection, using machine learning and simple heuristics to identify the features most important to classifying a meme as hateful. In the process, we build a gradient-boosted decision tree and an LSTM-based model that achieve comparable performance (73.8 validation and 72.7 test auROC) to the gold standard of humans and state-of-the-art transformer models on this challenging task.

For a graph $G$, let $f(G)$ denote the size of the maximum cut in $G$. The problem of estimating $f(G)$ as a function of the number of vertices and edges of $G$ has a long history and was extensively studied in the last fifty years. In this paper we propose an approach, based on semidefinite programming, to prove lower bounds on $f(G)$. We use this approach to find large cuts in graphs with few triangles and in $K_r$-free graphs.