Comparing computational entropies below majority
(or: When is the dense model theorem false?)

We turn to discuss the dense model theorem in some more detail to better contextualize our work. Restricting our attention to random variable over $\{0,1\}^{n}$, the dense model theorem states the following:

We will generally also consider a parameter $\varepsilon^{\prime}$, which in this case is $\varepsilon\delta$, the additive error in pseudodensity. To get an intuition for what this is saying, let’s conisder a setting where it’s false but for trivial reasons. As a simple example given in [52], pick a set $\mathbf{Z}$ some set as a $(1-\varepsilon)$ fraction of another set $\mathbf{S}$ of size $\delta 2^{n}$. Then $\mathbf{Z}$ doesn’t have a $\delta$-dense $\varepsilon$-model (i.e. $\mathbf{S}$) with respect to $\mathbf{Z}$’s indicator function, which we’ll call $f$. On the other hand, the distribution $\mathbf{W}$ obtained by sampling $\mathbf{Z}$ with probability $\delta$ and sampling from $\mathbf{S}$’s complement with probability $1-\delta$ is at most $\varepsilon\delta$-distinguishable from $\mathbf{S}$ for any function, since $\varepsilon\delta$ is simply the measure of the difference between $\mathbf{S}$ and $\mathbf{Z}$. In particular $\mathbf{Z}$ is $\delta$-dense in the $\varepsilon\delta$-pseudorandom $\mathbf{W}$ (which implies, via 1.1, that it is $(\varepsilon\delta,\delta)$-pseudodense). This means that the 1.1 is tight for the dependence on $\varepsilon^{\prime}=\varepsilon\delta$, in that it becomes false for $\Omega(\varepsilon\delta)$. In many instances, we think of $\varepsilon=1/{\mathsf{poly}}(n)$, $\delta$ constant (or perhaps with mild dependences on $n$) and $\varepsilon^{\prime}=\delta\varepsilon$.

Originally, the dense model theorem was proved with a different (and stronger) assumption; namely, that $\mathbf{Z}$ is dense in a pseudorandom set. Green and Tao, in proving that the primes contain arbitrarily long arithmetic progressions, used it to the following effect: if $\mathbf{Z}$ are the prime numbers up to $n$, then its density is known to behave like $\Theta(1/\log n)$. On the other hand, Szemerédi [45] showed that sufficiently dense subsets of $\mathbb{Z}$ contain arbitrarily long arithmetic progressions. The best bounds for Szemerédi ’s theorem require density $\omega(1/\log\log n))$, which is much larger than the primes (see [16] and the recent [9] for more on the rich history on this and related problems). Not all is lost, however: the only property of dense sets that we’re interested in is that they contain arithemtic progressions. So Green and Tao construct a class $\mathcal{F}$ of tests which can ‘detect’ arithmetic progressions and under which the primes are dense inside of a $\mathcal{F}^{\prime}$-pseudorandom set (more on $\mathcal{F}^{\prime}$ later). By applying the dense model theorem, we conclude that the primes ‘look like’ a dense set (themselves having long arithemtic progressions) with respect to the class $\mathcal{F}$. As $\mathcal{F}$ detects arithmetic progressions, it must be the case that the primes possess them. Of course, many details need to be filled in, but we hope this example shows the reader the ‘spirit’ of the dense model theorem.

A primary source of interest in the dense model theorem is in the connections it shares with seemingly unrelated branches of mathematics and computer science. The original application was in additive number theory, but it was independently discovered and proved in the context of cryptography ([8, 14]). RTTV [38] and Gowers [17] observed proofs of the dense model theorem which use linear programming duality, which is in turn related to Nisan’s proof of the hardcore lemma from circuit complexity [28]. In fact, Impagliazzo [29] shows in unpublished work that optimal-density versions of the hardcore lemma due to Holenstein [26] actually imply the dense model theorem. Klivans and Servedio [32] famously observed the relationship betweeen the hardcore lemma and boosting, a fundamental technique for aggregating weak learners in machine learning [15]. Together with the result of Impagliazzo, this connection means that dense model theorems can be proved by a particular type of boosting algorithm. A boosting argument for the existence of dense models also gives us constructive versions of the dense model theorem, which are needed for algorithmic applications. Zhang [52] (without using Impagliazzo’s reduction from the dense model theorem to the hardcore lemma) used the boosting algorithm of [7] directly to prove the dense model theorem with optimal query complexity ($k$).

In addition to its connections to complexity, machine learning, additive number theory and cryptography, the dense model theorem (and ideas which developed from the dense model theorem, chiefly the approximation theorem of [49]), have been used to understand the weak graph regularity lemma of Frieze and Kannan [29], notions of computational differential privacy [36] and even generalization in generative adversarial networks (GANs) [5]. We now turn to discussing the complexity-theoretic aspects of the dense model theorem, specifically regarding our question of whether the $\mathsf{MAJ}_{k}$ from the statement is optimal.

As alluded to earlier, Green and Tao actually worked in a setting where $\mathcal{F}^{\prime}$ doesn’t ’need to compute majorities but where $\varepsilon\delta$ (that is, the distinguishing parameter in the pseudodensity assumption in the statement of 1.1) needs to be replaced by some $\varepsilon^{\prime}=\exp(-{\mathsf{poly}}(1/\varepsilon,1/\delta))$ (with $k={\mathsf{poly}}(1/\delta,1/\varepsilon)$ experiencing a small increase). We state this result, as proved in Tao and Zeigler [48] and stated this way in RTTV [38], for comparison. For a test class $\mathcal{F}$, let $\prod_{k}\mathcal{F}$ be the set of tests of the form $\prod_{i\in[k]}f_{i}$ for $f_{i}\in\mathcal{F}$.

Another important aspect of the dense model theorem is how the different assumptions are related. As mentioned, the original assumption was that $\mathbf{Z}$ is $\delta$-dense in an $\varepsilon$-pseudorandom set, but the proof can be extended to the case where $\mathbf{Z}$ is $(\varepsilon,\delta)$-pseudodense. 1.1 showed that the former assumption implies that latter assumption. When the dense model theorem is true, the latter also implies the former: simply apply the dense model theorem to $\mathbf{Z}$ which is $(\varepsilon,\delta)$-dense to obtain a $\delta$-dense $\varepsilon$-model. Then, by the first part of 1.1, we’re done.

First, we give examples of situations where these two notions are distinct. For example, we show in 1.4 and 1.5 that they are inequivalent when $\mathcal{F}$ is constant-depth polynomial size circuits or when $\mathcal{F}$ is a low-degree polynomial over a finite field. Note that a separation between pseudodensity and being dense in a pseudorandom set also implies a separation between pseudodensity and having a dense model, as being dense in a pseudorandom set is a necessary condition for having a dense model.

Second, we show that the dense model theorem is false even when we make the stronger assumption that the starting distribution $\mathbf{Z}$ is dense in a pseudorandom set. Specifically, in 1.3 we can show that some distributions $\mathbf{Z}$ are dense in a pseudorandom set but fail to have a dense model when $\mathcal{F}$ consists of constant-depth, polynomial size circuits.

Having contextualized our work some, we now turn to describe our contributions in more detail.

We separate the previously described notions of computational entropy, giving examples where the dense model theorem is false. We are able to prove different separations when $\mathcal{F}$ is constant-depth unbounded fan-in circuits, low-degree polynomials over a finite field, and, in one case, any test class $\mathcal{F}$ which cannot efficiently approximate majority (in some sense made explicit later on). The only known separation prior was between pseudodensity and having a dense model for bounded-width read-once branching programs, due to Barak et al. [8].

Let $\mathcal{C}(S,d)$ denote the class of unbounded fan-in, size $S$, depth $d$ circuits. We are generally thinking of $S={\mathsf{poly}}(n)$ and $d=O(1)$, which corresponds to the complexity class ${\mathsf{AC}}^{0}$. 1.3 shows that $\mathbf{Z}$ being $\delta$-dense in an $\varepsilon$-pseudorandom set need not imply that $\mathbf{Z}$ has a $\delta$-dense $\varepsilon$-model when the test class is $\mathcal{C}(S,d)$:

Recall that the dense model theorem is false when $\varepsilon^{\prime}=\Omega(\varepsilon\delta)$, which makes the restriction $\delta\geq\varepsilon^{\prime}/8$ extremely mild. A common regime is $\varepsilon=1/{\mathsf{poly}}(n)$, $\delta=O(1)$ and $\varepsilon^{\prime}=\delta\varepsilon=\Theta(\varepsilon)$, in which case this gives us (essentially) a lower bound of weakly exponential in $1/\sqrt{\varepsilon}\approx 1/\sqrt{\varepsilon^{\prime}}$.

Let $\mathbf{N}_{\alpha}$ denote the product distribution of $n$ Bernoulli random variables with success probability $1/2-\alpha$. Recall that density in a pseudorandom set readily implies pseudodensity, and one can use the dense model theorem to show the converse. We show that $(\varepsilon,\delta)$-pseudodensity need not imply $\delta$-density in an $\varepsilon$-pseudorandom set when the test class is $\mathcal{C}(S,d)$:

The dependence $\varepsilon^{\prime}$ means that we can take $\varepsilon^{\prime}$ exponentially smaller than $\varepsilon$ and still obtain a separation. This case corresponds to $\mathcal{F}$ being ‘very’ fooled by $\mathbf{N}_{\alpha}$ but still not being $\delta$-dense in a ‘mildly’ pseudorandom set. This result draws on a recent line of work in the pseudorandomness literature — often referred to as ‘the coin problem’ and studied in, e.g., [42, 12, 1, 46] — which concerns the ability of a test class $\mathcal{F}$ unable to compute majority has in distinguising $\mathbf{N}_{\alpha}$ and $\mathbf{U}$. We will discuss this connection in more detail during the proof overviews.

We prove a similar separation for degree-$d$ $\mathbb{F}_{p}$-polynomials (on $n$ variables), which generalizes (and uses techniques from) a recent result of Srinivasan [44] in the case where $\delta=1$. In this case, we think of a distribution $\mathbf{Z}$ as being $(\varepsilon^{\prime},\delta)$-pseudodense for degree-$d$ $\mathbb{F}_{p}$-polynomials when $\delta\Pr[P(\mathbf{Z})\neq 0]-\varepsilon^{\prime}\geq\Pr[P(\mathbf{U})\neq 0]$ for any degree-$d$ polynomial $P\in\mathbb{F}_{p}[X_{1},...,X_{n}]$ (noting that we are only evaluating $P$ over $\{0,1\}^{n}$).

This implies lower bounds for constant-depth circuits with ${\mathsf{MOD}}_{p}$ gates by the classical lower bounds of Razborov [37] and Smolensky [43]. Perhaps more interestingly, this holds even over non-prime fields. Also notably, there is no dependence on $\varepsilon^{\prime}\leq\varepsilon\delta$, so we can take it to be arbitrarily small.

We also prove a more general separation between pseudodensity and density in a pseudorandom set. This result, drawing from the work of [42], provides a more specific characterization of the sense in which dense model theorems are ‘required’ to compute majority.

Informally, this says that any $\mathcal{F}$ which can refute the pseudodensity of $\mathbf{N}_{\alpha}$ is only ‘a constant-depth circuit away’ from computing majority.

We discuss two general themes that appear consistently in the proofs and then discuss each of the main theorems in some more detail.

As before, let $\mathbf{N}_{\alpha}$ denote the random variable corresponding to the product of $n$ independent coins with bias $(1/2-\alpha)$. That is,

where $\mathrm{wt}(z)$ denotes the Hamming weight of $z$.

For a random variable $\mathbf{Z}$ over $\{0,1\}^{n}$ and $i\in[n]$, let $\mathrm{bias}_{i}(\mathbf{Z})=|\Pr[\mathbf{Z}_{i}=1]-\Pr[\mathbf{Z}_{i}=0]|/2$. Let $\mathcal{B}=\{z\mapsto z_{i}:i\in[n]\}$ be the set of monotone projections. A random variable $\mathbf{Z}=(\mathbf{Z}_{1},...,\mathbf{Z}_{n})$ is $\epsilon$-pseudorandom with respect to $\mathcal{B}$ precisely when each marginal $\mathbf{Z}_{i}$ has the property that $\mathrm{bias}_{i}(\mathbf{Z})=|\Pr[\mathbf{Z}_{i}=1]-1/2|\leq\varepsilon$ for each $i\in[n]$. In particular,

The (Shannon) entropy of a random variable is defined as

where $p_{\mathbf{Z}}$ is the probability density function corresponding to $\mathbf{Z}$. The Shannon entropy of random vector is sub-additive, in that $H(\mathbf{Z})\leq\sum_{i\in[n]}\mathbf{Z_{i}}$. When $\mathbf{Z}\in\{0,1\}$ and $\Pr[\mathbf{Z}=1]=p$, we use $h(p)=H(\mathbf{Z})=-(p\log p+(1-p)\log(1-p))$ to denote the binary entropy function.

The min-entropy is defined as

If $\mathbf{Z}$ is $\delta$-dense inside of $\mathbf{U}$, then its min-entropy is $n-\log(1/\delta)$ and for any random variable $\mathbf{Z}$, $H_{\infty}(\mathbf{Z})\leq H(\mathbf{Z})$.

By this latter inequality and subadditivity, the average entropy of $\mathbf{Z}$’s bits is at least $1-\log(1/\delta)/n$. Appealing to a quadratic approximation of binary entropy, we learn that the bias must be at most $\sqrt{\log(1/\delta)/n}$. This result has been referred to as Chang’s inequality and the Level-1 inequality, having been observed in different forms and with different proofs in, for example, [47, 11, 22, 31]. Because it is so simple, we provide a proof here:

It follows directly from 2.2 that if $\mathrm{bias}_{i}(\mathbf{Z}_{i})$ exceeds $\varepsilon+\sqrt{\log(1/\delta)}/n$ for every $i$, then $\mathbf{Z}$ does not have a $\delta$-dense $\varepsilon$-model with respect to the projections $\mathcal{B}$.

This is used for the separation in 1.3. We would also like a necessary condition for being dense in a pseudorandom set. Towards this end, we note that pseudorandom distributions for even very simple test classes have mild concentration properties.

The tails of a dense subset can’t be too much larger than the original distribution, by definition of density. This gives us a test for being dense in a pseudorandom set, which we specialize to $\mathbf{N}_{\alpha}$.

A restriction over $[n]$ is a function $\rho:[n]\to\{0,1,*\}$. Indices in $\rho^{-1}(*)$ can be thought of as unset and each other index as set. For another restriction $z$ so that $\rho^{-1}(*)\subseteq z^{-1}(\{0,1\})$, let $\rho\circ z\in\{0,1\}^{n}$ be defined by

Define the restricted function $f|_{\rho}:\{0,1\}^{\rho^{-1}(*)}\to\{0,1\}$ over $\rho$’s unset indices by

Let $R_{p}$ be the distribution on restrictions over $[n]$ obtained by setting $\rho(i)=*$ independently with probability $p$, and then setting each bit not assigned to $*$ a random bit. The switching lemma we use is due to Rossman [39], building on a long line of work [3, 23, 24, 30]:

By considering a random restriction $\boldsymbol{\rho}\sim R_{p}$ over $[n]$ and a random variable $\mathbf{Z}$ over $\{0,1\}^{n}$, the definition of a restricted function implies that

We make crucial use of two simple corollaries of the switching lemma, which allow us to reason about distinguishability for ${\mathsf{AC}}^{0}$ circuits in terms of distinguishability for short decision trees.