The upper logarithmic density of monochromatic subset sums

We show that in any two-coloring of the positive integers there is a color for which the set of positive integers that can be represented as a sum of distinct elements with this color has upper logarithmic density at least $(2+sqrt{3})/4$ and this is best possible. This answers a forty-year-old question of ErdH{o}s.

Spectral independence, coupling with the stationary distribution, and the spectral gap of the Glauber dynamics

We present a new lower bound on the spectral gap of the Glauber dynamics for the Gibbs distribution of a spectrally independent $q$-spin system on a graph $G = (V,E)$ with maximum degree $Delta$. Notably, for several interesting examples, our bound covers the entire regime of $Delta$ excluded by arguments based on coupling with the stationary distribution. As concrete applications, by combining our new lower bound with known spectral independence computations and known coupling arguments: (1) We show that for a triangle-free graph $G = (V,E)$ with maximum degree $Delta geq 3$, the Glauber dynamics for the uniform distribution on proper $k$-colorings with $k geq (1.763dots + delta)Delta$ colors has spectral gap $tilde{Omega}_{delta}(|V|^{-1})$. Previously, such a result was known either if the girth of $G$ is at least $5$ [Dyer et.~al, FOCS 2004], or under restrictions on $Delta$ [Chen et.~al, STOC 2021; Hayes-Vigoda, FOCS 2003]. (2) We show that for a regular graph $G = (V,E)$ with degree $Delta geq 3$ and girth at least $6$, and for any $varepsilon, delta > 0$, the partition function of the hardcore model with fugacity $lambda leq (1-delta)lambda_{c}(Delta)$ may be approximated within a $(1+varepsilon)$-multiplicative factor in time $tilde{O}_{delta}(n^{2}varepsilon^{-2})$. Previously, such a result was known if the girth is at least $7$ [Efthymiou et.~al, SICOMP 2019]. (3) We show for the binomial random graph $G(n,d/n)$ with $d = O(1)$, with high probability, an approximately uniformly random matching may be sampled in time $O_{d}(n^{2+o(1)})$. This improves the corresponding running time of $tilde{O}_{d}(n^{3})$ due to [Jerrum-Sinclair, SICOMP 1989; Jerrum, 2003].

Subset sums, completeness and colorings

We develop novel techniques which allow us to prove a diverse range of results relating to subset sums and complete sequences of positive integers, including solutions to several longstanding open problems. These include: solutions to the three problems of Burr and ErdH{o}s on Ramsey complete sequences, for which ErdH{o}s later offered a combined total of $350; analogous results for the new notion of density complete sequences; the solution to a conjecture of Alon and ErdH{o}s on the minimum number of colors needed to color the positive integers less than $n$ so that $n$ cannot be written as a monochromatic sum; the exact determination of an extremal function introduced by ErdH{o}s and Graham on sets of integers avoiding a given subset sum; and, answering a question reiterated by several authors, a homogeneous strengthening of a seminal result of Szemeredi and Vu on long arithmetic progressions in subset sums.

Regularity method and large deviation principles for the ErdH{o}s--Renyi hypergraph

We develop a quantitative large deviations theory for random Bernoulli tensors. The large deviation principles rest on a decomposition theorem for arbitrary tensors outside a set of tiny measure, in terms of a novel family of norms generalizing the cut norm. Combined with associated counting lemmas, these yield sharp asymptotics for upper tails of homomorphism counts in the $r$-uniform ErdH{o}s--Renyi hypergraph for any fixed $rge 2$, generalizing and improving on previous results for the ErdH{o}s--Renyi graph ($r=2$). The theory is sufficiently quantitative to allow the density of the hypergraph to vanish at a polynomial rate, and additionally yields (joint) upper and lower tail asymptotics for other nonlinear functionals of interest.

On the sampling Lovasz Local Lemma for atomic constraint satisfaction problems

We study the problem of sampling an approximately uniformly random satisfying assignment for atomic constraint satisfaction problems i.e. where each constraint is violated by only one assignment to its variables. Let $p$ denote the maximum probability of violation of any constraint and let $Delta$ denote the maximum degree of the line graph of the constraints. Our main result is a nearly-linear (in the number of variables) time algorithm for this problem, which is valid in a Lovasz local lemma type regime that is considerably less restrictive compared to previous works. In particular, we provide sampling algorithms for the uniform distribution on: (1) $q$-colorings of $k$-uniform hypergraphs with $Delta lesssim q^{(k-4)/3 + o_{q}(1)}.$ The exponent $1/3$ improves the previously best-known $1/7$ in the case $q, Delta = O(1)$ [Jain, Pham, Vuong; arXiv, 2020] and $1/9$ in the general case [Feng, He, Yin; STOC 2021]. (2) Satisfying assignments of Boolean $k$-CNF formulas with $Delta lesssim 2^{k/5.741}.$ The constant $5.741$ in the exponent improves the previously best-known $7$ in the case $k = O(1)$ [Jain, Pham, Vuong; arXiv, 2020] and $13$ in the general case [Feng, He, Yin; STOC 2021]. (3) Satisfying assignments of general atomic constraint satisfaction problems with $pcdot Delta^{7.043} lesssim 1.$ The constant $7.043$ improves upon the previously best-known constant of $350$ [Feng, He, Yin; STOC 2021]. At the heart of our analysis is a novel information-percolation type argument for showing the rapid mixing of the Glauber dynamics for a carefully constructed projection of the uniform distribution on satisfying assignments. Notably, there is no natural partial order on the space, and we believe that the techniques developed for the analysis may be of independent interest.

Mixing time of fractional random walk on finite fields

We study a random walk on $mathbb{F}_p$ defined by $X_{n+1}=1/X_n+varepsilon_{n+1}$ if $X_n eq 0$, and $X_{n+1}=varepsilon_{n+1}$ if $X_n=0$, where $varepsilon_{n+1}$ are independent and identically distributed. This can be seen as a non-linear analogue of the Chung--Diaconis--Graham process. We show that the mixing time is of order $log p$, answering a question of Chatterjee and Diaconis.

Towards the sampling Lovasz Local Lemma

Let $Phi = (V, mathcal{C})$ be a constraint satisfaction problem on variables $v_1,dots, 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 [Ccdot q^{3}cdot k cdot p cdot Delta^{7} < 1, quad text{where }C text{ 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 et al., arXiv, 2020]. 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 et al., SICOMP, 2019] and $Delta^{9}$ for randomized algorithms [Feng et al., arXiv, 2020].