Introduction

For a finite universe U , a class F of bounded tests f : U → [0, 1] and measure µ : U → [0, 1] over U , we say that another measure ν : U → [0, 1] is an ε-model of µ, for 0 < ε, with respect to F if for any f ∈ F,

that is, if µ and ν are ε-indistinguishable with respect to F. Producing simple models of data turns out to be a central task in theoretical computer science and beyond. For example, the construction of pseudorandom generators can be understood as producing explicit, efficiently samplable models of the uniform distribution with respect to a class of computationally-bounded tests. Even in practice, modern machine learning employs the use of generative models to automatically produce simple models of complex data sets and the notion of distinguishability has been used to explain generalization in this setting [Risteki, Arora papers]. It therefore becomes natural to ask for generic conditions under which simple models of data exist.

Dense model theorems, originally developed in the context of additive number theory, provide a set of sufficient conditions under which µ has a model which is dense with respect to the underlying universe U and has enjoyed a variety of applications. The original application, for example, was the Green-Tao theorem on arithmetic progressions of primes [GT08]. There, it was used to enable an application of Szemerédi's theorem on a 'dense model' of the prime numbers with respect to tests encoding useful additive information. In computer science, it has been, for example, used in leakage-resilient cryptography [cite], differential privacy [cite] and connected to proofs of the hardcore lemma and weak graph regularity lemma [Rei+08].

To formally define such a result, we'll need a few more definitions. For a measure µ : U → [0, 1], we say that µ is δ-dense if E[µ] = δ. Additionally, we say that µ is (δ, γ)-pseudodense with respect to F if

Then a dense model theorem can be defined as follows:

Definition 1. For a finite universe U and a bounded class of tests F of the form f : U → [0, 1], any ε, δ > 0, and k = k(ε, δ), γ = γ(ε, δ), an (ε, δ, γ, k)-dense model theorem for F over U states the following:

Let µ : U → [0, 1] be a measure over U . Then exactly one of the following hold:

1. There's a δ-dense measure ν so that µ and ν are ε-indistinguishable by F.

2. There are k tests f 1 , ..., f k ∈ F and a function g : [0, 1] k → [0, 1] so that the map x → g(f 1 (x), ..., f k (x)) refutes the (δ, γ)-pseudo-density of µ.

We'll generally refer to the δ-dense measure ν as a dense model of ν and the function g as a refuter of g's pseudo-density.

There are essentially two parameter regimes for which dense model theorems are known. The first, appearing in the work of Green-Tao [GT08] and Tao-Ziegler [TZ08], has γ exponentially small in ε and δ but a computationally simple witness g. They use an iterative partitioning approach, similar in spirit to Szemerédi's proof of the graph regularity lemma.

Theorem 2 (Green-Tao-Ziegler). For any finite universe U , any set of bounded functions F of the form f : U → [0, 1] and any ε, δ > 0, there's an (ε, δ, γ, k)-dense model theorem for F over U with k(ε, δ) = poly(1/ε, 1/δ), γ(ε, δ) = exp(-poly(1/ε, 1/δ)), and g(x 1 , ..., x k ) = k i=1 x i .

The second setting, shown independently by Gowers [cite] and Reingold, Trevisan, Tulsiani and Vadhan [Rei+08], obtains a γ with polynomial dependence on ε and δ but uses a more complex function g. Proofs using linear programming duality or boosting are known.

Theorem 3 (RTTV, Gowers). For any finite universe U , any set of bounded functions F of the form f : U → [0, 1] and any ε, δ > 0, there's an (ε, δ, γ, k)-dense model theorem for F over U with k(ε, δ) = O(log(1/δ)/ε 2 ), γ(ε, δ) = O(εδ), and g(x 1 , ..., x n ) = sign(-t + k i=1 ±x i ).foot_0

In the latter case, it can be shown that when a dense model ν does indeed exist, it can be written in the form ν(x) = k i=1 w i f i (x) for weights w i ∈ R and f i ∈ F. We're now in a position to frame the question underlying this work -what does it mean for a dense model theorem to require majority? Answering this can be explained in terms of the following more qualitative description of a dense model theorem: either a distribution has a simple, dense model or there is an explanation as to why it doesn't. The two natural notions of computational complexity here are the the simplicity of the explanation as to why the input measure fails to have a dense model or the simplicity of the dense model itself. In both cases, we'll prove lower bounds that roughly match the known upper bounds.

Regarding the first notion of complexity, we borrow an approach from Shaltiel and Viola for proving complexity lower bounds on hardness amplification proofs, and show that any 'explanation' that the distribution of n independent biased coin tosses fails to be pseudo-dense can be used in a constant-depth oracle circuit computing majority. Specifically, let N η be the product of n Bernoulli random variables Ber(p) with p = 1/2 -η. Then, Theorem 4 (Informal). Let U = {0, 1} n and F be the set of functions x → x i for each i ∈ [n]. For any ε, δ, γ and η ≈ η, 1. N η is ε-distinguishable from every δ-dense measure by F.

2. Any g : {0, 1} n → {0, 1} which refutes the (δ, γ)-pseudo-density of N η can be used in a constantdepth oracle circuit C of size poly(δ 2 /η 3 γ 3 ) so that C computes the majority on inputs of length O(1/η) where η ≈ ε.

The first thing to note is the similarity to the result of Shaltiel and Viola [SV10]: they provide an AC 0 -Turing reduction from majority to the coin problem -distinguishing between the biased distribution and the uniform distribution -and further show that (non-adaptive, later improved to adaptive in [GSV18]) black-box hardness amplification procedures produce algorithms for solving the coin problem. This similarity is of course no coincidence, given the relationship between the hardcore lemma (an instance of hardness amplification) and the dense model theorem. Indeed, that dense model theorems require majority (in terms of g's complexity) could be deduced as a corollary of their result if we had a reduction from hardcore lemmas to dense model theorems. While there is a reduction in the other directionan optimal hardcore lemma implies a dense model theorem -the other direction remains unclear. We circumvent this by designing a reduction directly from dense model theorems to the coin problem.

Note also that the condition of booleanity on g is essentially without loss of generality: if we had a bounded test g : [0, 1] k → [0, 1] which refutes the pseudo-density of a measure µ, we can convert g into a boolean-valued refuter g so that

To do so, let C be a randomized circuit that does the following: on input x, it computes (a dyadic approximation of) g(x) and then flips a coin with bias g(x) and outputs the result. Then the probability over C and x that C(x) = 1 is simply E x [g(x)], with a small amount of error introduced by approximating g(x) with finite precision. Non-uniformly, we can then average out the randomness to get a deterministic circuit. This conversion was observed before in [TTV09].

For the second notion of complexity, it is relatively straightforward to get some type of lower bound on the complexity of the model. For example, let F be the class of delta functions δ x (y) = 1 iff. y = x for each x ∈ {0, 1} n . Then by taking µ to be the 1s of majority, any ε-approximation ν of µ with respect to F has the property that for all x, |ν(x)-µ(x)| ≤ ε. Specifically, ν is an ε-approximation of µ in the ∞ -norm. From here, it is known that any polynomial p which ε-approximates µ point-wise must have high degree (see, e.g., Paturi), and therefore ν must have high-degree. However, this approach doesn't explain the structure of g in a very useful way: even the g used in the Green-Tao proof has high approximate degree. Additionally, an ideal example would make the difference in the complexities of F and g • F as large as possible.

For a stronger example, we'll still choose µ to itself be a linear threshold function with integer weights but now take F be the set of functions x → x i for i ∈ [n]. A simple Fourier-analytic argument tells us that any model of µ must be correlated with µ, as F, by definition, detects large-enough differences in the linear Fourier coefficients:

Theorem 5 (Informal). Let U = {-1, 1} n and F be the set of projections. Then for each δ > 0 and ε sufficiently small, there's a measure µ : {-1, 1} n → {0, 1} so that 1. µ is a linear threshold function with integer weights. That is, µ(x) = sign(-θ + m i=1 w i x i ) for some parameters θ, w 1 , ..., w n ∈ Z.

2. µ is δ-dense (and therefore (γ, δ)-pseudodense with respect to g • F for any g).

If

Indeed, work on the Chow parameters problem allows us to pick any linear threshold function as an example. Specifically, [cite, cite] show that if the linear Fourier coefficients of µ and ν are close where µ is linear threshold function, then µ and ν are actually close in 1 -distance.

Trevisan, Tulsiani and Vadhan noticed that dense model theorems are a special case of a more general result, a type of decomposition theorem, which explains that any bounded function f : U → [0, 1] can be approximated by a function g of 'constant' complexity, in the sense that f is indistinguishable from g by tests F and g built out of a small combination of functions in F, the size of which is independent of |U |. Specifically, Theorem 6 (Decomposition theorem, [TTV09]). Let U be a finite universe, F a set of bounded tests f : U → [0, 1] and µ : U → [0, 1] a measure over U . Then there exists a measure ν with Eν = Eµ so that 1. ν can be built out of k = poly(1/ε) functions f 1 , ..., f k ∈ F using multiplication by a constant, sums, products and linear threshold functions.

2. µ and ν are ε-indistinguishable with respect to F.

Informally, this says that simple tests can be fooled by distributions which are almost as simple, and the dense model theorem, the hardcore lemma and the weak graph regularity lemma all follow as corollaries. It is simple to see that our example also provides a lower bound on the complexity of the approximator ν, explaining that, in some cases, there is a necessary gap between the tests F and and distributions which fool them.

Preliminaries

for all x ∈ {0, 1} n . Note that this is equivalent to having min-entropy at most n -log(1/δ). We first note the smooth distributions and dense measures are interchangable. Lemma 7. A measure µ has density at least δ if and only if the distribution X µ defined by

Proof. For the forward direction, note that

The distribution X µ can be sampled by rejection sampling according to µ. As the distinction will always be clear from context, we will hereafter abuse notation and avoid distinguishing between the measure µ and the distribution X µ induced by µ.

Indeed note that f refuting the

-γ, clearly implies that U and N η are η-indistinguishable by f and in particular f solves the η-coin problem with advantage γ.

Let N η denote the distribution on {0, 1} n obtained by sampling n

The connection Fourier analysis is simple: for both claims, we'll be interested in the class of tests of the form x → x i which are simply the linear characters of F n 2 . Specifically, the bias of the map x → x i when x is drawn from a measure µ is exactly the Fourier coefficients µ(i).

Proof overviews

Refuting pseudo-density requires majority

We begin with the simple observation that for any 1/2 > η > 0 sufficiently large, the noise distribution N η satisfies the promise of the dense model reduction in that N η is distinguishable from dense distribution with significant advantage, so long as our test class contains monotone projections x → x i for each i ∈ [n]. This follows by a simple observation -made many times before -that any dense distribution over {0, 1} n has a bit which is relatively unbiased. Then by the dense model theorem, we are left with a family of tests which refute the pseudo-density of N η for any sufficiently large η, which we'll use to build our majority circuit.

To do so, we'll largely follow the reduction from majority to the coin problem from Shaltiel-Viola with a minor modification. Since any f solving (η, δ, γ)-coin-density problem also solves the η-coin problem with advantage γ, we might hope to employ the following construction from Shaltiel and Viola: Lemma 8 ([SV10]). Suppose A solves the η-coin problem with advantage γ, where γ ≥ 1/ log(1/η). Then there's an AC 0 circuit with oracle access to R solving majority on inputs of length 1/η.

The technicality that arises is the dependence on γ. In our context, we need to think of η > ε and therefore γ will need to be exponentially larger than ε. However, a straightforward construction shows that the dense model theorem is actually false in this regime, as observed by Zhang in [Zha11].

Claim 9 ([Zha11]

). There is no (ε, δ, γ)-dense model reduction for any γ > εδ.

Proof. Let µ ⊆ U be a set of size δ(1 -ε)|U | and let the class of tests solely consist of the characteristic function of µ, call it f . Then 1. There's no δ-dense ε-model of µ with respect to f . This is because Pr T [f (x) = 1] ≤ 1 -ε, as any such δ-dense ν has to cover a (1 -ε)-factor larger subset of the universe.

2. µ is (δ, δε)-pseudodense with respect to any test g

Fortunately, we have a stronger guarantee than distinguishing the noise distribution from uniform, as the acceptance probabilities are bounded away by a multiplicative constant δ.

We will use this stronger assumption roughly as follows: let w < 1/2η and suppose that A w solves the (wη, δ, γ)-coin-density problem. We'll build a randomized algorithm S w : {0, 1} 1/η → {0, 1} so that for α := Pr[S w (x) = 1| x has weight 1/2η], β := Pr[S(x) = 1| x has weight w], we have α ≤ δβ -γ. By independently sampling g w , we'll produce a test Sw : {0, 1} n → N so that S w (x) ≤ δβm when x has weight 1/2η and S w (x) ≥ βm when x is balanced (for an appropriate choice of m). Thus, a relativeerror approximate majority circuit, implementable in AC 0 , can successfully distinguish these two cases. 2From here, we can combine S w for each w < 1/2η into a simple depth-2 circuit, the result of which computes majority. This approach follows Shaltiel-Viola almost exactly, with the difference being the use of a relative-error approximate majority circuit as opposed to their use of an additive-error approximate majority circuit. Since they begin with only an additive distinguishing gap, they need an additive-error approximate majority circuit, which in turn produces the undesirable dependence on γ.foot_2

Modeling sometimes requires thresholds

Let B be the Hamming ball centered on 1 n with density δ. Any δ-dense model ν of B with respect to bit queries has the property that | ν(i) -B(i)| ≤ 2ε, where ν(i) denotes the ith linear Fourier coefficient of ν.

We would like to show that this implies that ν and B are actually correlated. Note that this isn't tautological because having a model according to F does not imply correlation. Specifically, we could take f to be a random function and still model it with respect to constantly-many functions F combined with linear threshold functions (see [TTV09]) and yet they won't be correlated. Modeling simply means that F can't reliably detect the differences between f and its model.

A simple claim from Birkendorf et al. tells us that this is indeed that case when ε is sufficiently small:

Applying this directly gives the desired conclusion for small ε.

Note that this claim has no dependence δ, which in this example is roughly 2 -t 2 (thinking of B as a set). For larger ε, we can make a similar argument where now the error depends on δ:

Then

2 Refuting pseudo-density requires majority

Dense measures have nearly-unbiased bits

Claim 12. For any δ-dense distribution ν, there's some index i ∈

Averaging, there's some i so that | ν(i)| ≤ 2δ 2 log(1/δ)/n. Note that

and hence Pr ν [x i = 1] = 1/2 ± ν(i)/2, which gives us the desired conclusion.

We can immediately conclude the following.

Corollary 13. For any δ-dense distribution ν with δ < 1, there is a test T of the form x → x i which ε-distinguishes between N η and ν for any

Proof. Let i be the index from the previous claim. Then x → x i ε-distinguishes between N η and ν for η

Let ε, δ, γ, η * = ε + δ 2 log(1/δ)/2n be fixed. The previous claim says that if the (ε, δ, γ)-dense model theorem over {0, 1} n with tests containing monotone projections is true, then we can apply it to the noise distribution N η for any η ≤ η * and in turn produce an algorithm for the (η, δ, γ)-coin density problem. We'll now argue oracle access to these algorithms can be used in an AC 0 circuit computing majority.

Solving majority with the coin-density problem

Suppose we have an algorithm A for the (η, δ, γ)-coin density problem for every η < η * for some fixed η * . We proceed in steps:

1. Let w < 1/(2η * ). We'll produce a distribution S over functions s : {0, 1} 1/η * → {0, 1} so that Pr[s(y) = 1] ≤ δ Pr[s(z) = 1] -γ for every balanced y ∈ {0, 1} 1/η * and every z ∈ {0, 1} 1/η * with weight w.

2. Using an approximate majority construction, we will reduce the error of the previous algorithm. Specifically, we'll produce an algorithm S so that S(y) = 0 whenever y is balanced and S(z) = 1 whenever z has weight w.

3. Repeating this construction for each w < 1/(2η * ) to obtain algorithms S w as above, we can see that C(x) = ∧ w ¬S w (x) is 1 when x is balanced and 0 when x has weight less than 1/(2η * ).

4. Finally, let x i denote x with the first i bits of x set to 0. Then C (x) = ∨ i≤1/(2η * ) C(x i ) is 1 if there's an i so that x i is balanced, which characterizes majority: if x is low weight, then all of its restrictions x i are also low weight. If x has high weight, then there's a restriction x i which is balanced.

Once again, this approach is identical to Shaltiel and Viola [SV10], except for our error reduction step. The following simple claim from [SV10] verifies the correctness of the construction conditioned on steps 1 and 2 being correct.

Claim 14 ([SV10]

). Suppose for each w < 1/(2η * ), S w : {0, 1} 1/η * → {0, 1} has the property that S w (x) = 0 when y is balanced and S (z) = 1 whenever z has weight w. Then the depth-two oracle circuit C (with oracle access to S w for each w < 1/(2η * )) of size 1/(2η * ) 2 with 1/(2η * ) oracle calls defined by

computes majority.

We'll now proceed to establishing the first two steps. First we have a randomized reduction from the coin-density problem to the promise problem of distinguishing between balanced and unbalanced strings.

Claim 15 ([SV10]

). Let 1 ≤ w < 1/(2η * ) and suppose A solves the (1/2 -wη * , δ, γ)-coin density problem (so the bias of each coin in the noisy distribution is w/η * ). Then there's a randomized test S : {0, 1} 1/η * → {0, 1} with the following property:

Proof. Let i 1 , ..., i n denote independent random variables which are uniform over the co-ordinates [1/η * ]. Then define S(x) ≡ A(x i 1 , ..., x in ). For balanced y, y i 1 , ..., y in is distributed as N 0 , and for z with weight w, z i 1 , ..., z in is distributed as N 1/2-wη * . The conclusion follows since A solves the (1/2 -wη * , δ, γ)-coin problem.

Note that since wη * ≤ 1/2 -η * and we have solutions to the coin problem for each η < η * , the assumption from the previous claim is satisfied for any choice of 1 ≤ w < 1/(2η * ). This step is what restricts the input size to be 1/η * . More generally, for a fixed length , we could pick any weights w so that w/l ≤ 1/2 -η * i.e. so that difference in weights is at least η * . This approach is outlined in [Srikanth's coin problem paper] by picking ≈ (1/η * ) 2 meaning that w can range up to roughly /2 -√ . This can be used to approximate majority (that is, the correlation problem) since most strings with weight at most /2 lie outside of the interval [ /2 -√ , /2). For applications to circuit lower bounds, this yields stronger parameters.

Does this work in our case? I think we can actually employ the same idea, but we still need to do the error reduction, whose complexity is going to be poly(1/γ), and we'd still get only an approximation of majority. Still, I think this will give us better explicit lower bounds as the input length is significantly bigger.

Next, we perform a non-uniform error reduction to make S deterministic using two steps. First, we reduce to the problem of distinguishing strings in {0, 1} m of weight roughly δβm from βm for an appropriate choice of m. Second, we solve this distinguishing problem in AC 0 using a relative-error approximate majority construction.

Claim 16 (Shaltiel-Viola). Let S be from Claim 12. For any ∆ > 0, there are m = O( 1 η * ∆ 2 α ) tests s 1 , ..., s m with the following properties:

Proof. Suppose y is balanced and z has weight wη * and consider drawing m samples S 1 , ..., S m from S. By the Chernoff bound,

both of which are bounded by 2 -1/η * by taking m ≥ O(1/(η * ∆ 2 α)). The union bound therefore tells us that the probability over our samples that every balanced string's sum is small and every unbalanced string's sum is large is more than 0, meaning in particular that some choice of samples s 1 , ..., s m realizes the desired properties.

Let Θ = δβ δβ-γ and let ∆ = Θ-1 Θ+1 = γ 2δβ-γ . Doing so means that (δβ -γ)m(1 + ∆) = δβm(1 -∆) and in particular our we'll distinguish weight k = βm(1-∆) strings from weight δk strings, setting up the relativeerror approximate majority problem. 4 We will solve the relative-error approximate majority problem with pairwise independent hashing, essentially following the construction of Stockemeyer's theorem for counting NP witnesses from [Sto83].

The following is a standard concentration bound for pairwise independent hash functions.

Lemma 17. Let H be a family of pairwise independent hash functions h :

Pr

In particular, when We can apply this directly to distinguish between high weight and low weight strings by hashing and counting the number of collisions.

Claim 18. Let r = δk/16, H a family of pairwise independent hash functions h :

For these tests to be mutually exclusive, we require that 24 < 16 δ -8 √ δ or that δ < 4/9, excluding, for example, the case where δ = k-1 k which is known to be intractable for AC 0 circuits (see, e.g., Hastad's thesis). Note that implementing this only requires counting up to a constant, as we're not concerned with the behavior of the test when the input doesn't satisfy the promise of being weight k or weight δk.

Since we're hashing the input co-ordinates, this test can be easily implemented in AC 0 . Constructions of pairwise independent families h : {0, 1} log m → {0, 1} log r with size |H| = m • r are known by taking, e.g. linear functions over finite fields. Specifically, we can consider m = 2 s and r = 2 t , and then consider the first t bits of the function h a,b (x) = a • x + b, thinking of a, b, x ∈ F 2 s . Since s = log m, we can perform finite field arithmetic with an AC 0 circuit polynomial size in m. We then apply the hash function to each co-ordinate i so that the ith input bit is 1, and count the number of co-ordinates which hash to 0.

TO-DO: specify the depth of computing h We therefore get the following claim:

Claim 19. There's a depth-d =?, randomized AC 0 circuit of size poly(m) that distinguishes between weight δk and weight k strings in {0, 1} m with probability at least 3/4.

From here, there's two approaches towards derandomization. The first approach is to reduce the error our construction from 1/4 to O(1/(η * ) 2 ) from which we can get a circuit which approximates majority on some large constant fraction of inputs. This still suffices for AC 0 [⊕] and AC 0 lower bounds.

A less efficient approach can give us a perfect derandomization: since |H| being polynomial in m allows us to derandomize the construction by an exhaustive search and then taking an additive approximate majority circuit, distinguishing between relative weights of 1/4 and 3/4 , for which efficient AC 0 constructions are known (e.g. Ajtai [Ajt83] or Viola [Vio09]). This increases the depth of the construction by 3.

We could also reduce the error from 1/4 to roughly

) and then union bound over the randomness, but then the hashing test itself seems to be hard for AC 0 .

Theorem 20 ([Ajt83], [Vio09]

). There exists a family of polynomial-size AC 0 circuits of depth 3 distinguishing between relative weight 1/4 strings and relative weight 3/4 strings.

As explained above, we can apply such an approximate majority circuit to the output of the tests s 1 , ..., s m from Claim 14 to distinguish between weight wη * and weight 1/2η * strings in {0, 1} 1/η * , can then be used in steps 3. and 4. to complete the reduction.

We're now left with computing m.

Of course, α could be small (or even 0) which in our case could be problematic. We can fix this by replacing the randomized test S with the test S which outputs S(x) with probability 1 -σ and outputs 1 with probability σ. The new acceptance probabilities α = α + σ and β + σ will continue to satisfy the pseudo-density relation so long as

, meaning we can assume with no loss of generality that the pseudo-density inequality is satisfied with equality with no affect on the previous analysis. This gives us:

,

is the new acceptance probability for unbalanced strings by setting σ. Finally, we can take β to be a constant by taking the 'OR' of sufficiently-many independent copies of S .

Claim 21. There's a randomized test S so that α ≤ δβ -γ where

Proof. Draw p independent tests s 1 , ..., s p from S . Then if x has weight wη * , then by inclusion-exclusion we have Pr s 1 ,...,sp

which is a constant when p = O(1/β ). By construction of S , we had β = (γ + α)/δ.

We can therefore estimate m = O( δ η * γ 2 ). To compute the total size of the circuit, we have O((1/η * ) 2 ) calls to S from steps 3. and 4. and O(δ/γ) calls to S for each call to S . Moreover, S is derandomized using a depth-6, poly(m)-size AC 0 circuit. Putting this together yields: Claim 22. Suppose for each η ≥ η * , there's an algorithm A η solving the (η, δ, γ)-coin-density problem on inputs of length n. Then there's a size-s, depth-d AC 0 circuit using oracle access to the A η 's computing majority on inputs of length 1/η * , where s = poly( δ 2 (η * ) 3 γ 3 ) and

3 Measures whose models require thresholds

We will once again take our tests F to to be bit queries, but we'll think of our universe as U = {-1, 1} n . In this setting, it's easy to see the following claim:

Now we'll choose µ to be the extremal case of µ(i) for subsets of {0, 1} n with a fixed density. Our example B δ will be the 'heaviest' subset of {-1, 1} n with density δ. Specifically, note that, by the Chernoff bound, threshold functions of the form Thr t (x) = sign(-t √ n + n i=1 x i ) have density 2 Θ(-t 2 ) . Then we'll take B δ = Thr t with t = n log(1/δ). We can now see that B δ is indeed the extremal case of µ(i):

Proof. To-do...

A simple Fourier-analytic argument explains that, since B := B δ is a linear threshold function with integer weights, any ν whose linear Fourier coefficients are close to B's is actually close to B in distance. On the other hand, (again by Plancherel's) Note that this holds independent of the density of the approximation ν. Using the density, we can get a similar argument where the error now depends on δ. When δ is large, this is less restrictive in terms of ε.

Proof. Assume towards a contradiction that dist(ν, B) ≥ δ/2, where B = 1-B. If we reach a contradiction then we can conclude the proof as follows: otherwise, dist(ν, B) ≥ δ/2. Then, since B is δ-dense, ν incurs at most δ/2 error on B and, since ν is δ-dense, ν incurs at most δ/2 error on B, which gives us the desired claim.

To see the contradiction, note that

and so

For simplicity, write β = B(i) = -2δ 2 log(1/δ)/n. Then by averaging, there's some i ∈ [n] so that

Since ν(i) ≤ β would already be a contradiction of the fact that ν is a model for B, we get

which is a contradiction (remember B's bias is -β) so long as

Implicit in this claim is an argument that closeness in function space implies closeness of the linear Fourier coefficients. This argument has appeared before in [O'Donnell, Servedio, chow parameters problem].

Russell mentioned another claim if we look at B δ and B δ for δ > δ, then most of ν needs to lie on the correct side of B δ . This appears to be the same argument: if I lied too much on the wrong side of B δ , I would be too close to B δ so that my bias would be too small Proof. Consider B δ and B δ and a δ-dense ε-model ν of B δ . Suppose that dist(ν, B δ ) ≥ γ for some γ. Then It is easy to see that the same example applies to the decomposition lemma of Trevisan, Tulsiani and Vadhan [TTV09].

Applications

Explicit circuit lower bounds

Recall the following worst-case lower bounds from circuit complexity: Theorem 28 ([Raz87], [Smo87], [Has86]).

1. Any depth-d AC 0 [⊕] circuit computing majority has size 2 Ω(n 1/2(d-1) ) .

2. Any depth-d AC 0 circuit computing majority has size 2 Ω(n 1/(d-1) ) .

Given the poly( δ 2 γ 3 η * 3 ) bound on the size of an AC 0 circuit computing majority with oracle access to a pseudo-density refuter, we can prove explicit circuit lower bounds on pseudo-density refuters. Suppose we substitute the oracle for an explicit C ∈ {AC 0 , AC 0 [⊕]} circuit which implements a dense-model reduction as above. If it has size s and depth d, then we obtain a C circuit computing majority of depth d + 6 and size O(s • δ 2 γ 3 η 3 ). We therefore get the following corollaries: Additionally, we have correlation bounds on linear threshold functions for AC 0 circuits and AC 0 [⊕]:

Theorem 29.

1. F 2 -degree bounds on linear threshold functions 2. AC 0 -correlation bounds on linear threshold functions Most of the references just look at majority, so let's look at B δ instead as a function of δ. Of course, if δ is very far from 1/2, then it will be easy because the function will be sparse.

Simple proofs of lower bounds for hardcore lemmas and boosting

We'll present simple proofs that hardcore lemmas and boosting require majority by reduction from dense model theorems. Both of these results can be deduced from [SV10], but our proofs are arguably simpler, since they avoid having to a construct a solution to the coin problem from a hardness amplification proof.

Hardcore lemmas require majority

The first application we present leverages the connection between dense model theorems and hardcore lemmas due to Impagliazzo in [Imp19]. 5 Recall that the hardcore lemma, originally appearing in [Imp95], is an approach to hardness amplification and can be used to, for example, prove Yao's XOR lemma. It states that if we have a function f which mildly hard for circuits of size s, then there's a dense set of the inputs on which f is extremely hard for circuits of size s slightly smaller than s. We'll define a hardcore lemma in the contrapositive: using that f is very mildly approximated by a circuit of s over any dense set of the inputs, we'll build, in a black-box fashion, a good approximation of f over the uniform distribution by a circuit of size s slightly larger than s .

Before stating the lemma, we'll fix some notation. A function f γ-approximates a function g over a distribution D if Pr x∼D [f (x) = g(x)] ≥ γ. We'll informally refer to a strong approximation as something like a γ-approximation when γ = 1 -δ, thinking of δ as small. Similarly, a weak approximation will refer to a (1/2 + ε)-approximation, again thinking of ε as small. A function f is γ-hard over D for a class of tests T if Pr x∼D [T (x) = f (x)] ≤ 1 -γ for any T ∈ T .

Definition 30 (Black-box hardcore lemma). A (ε, δ, k)-black-box hardcore lemma reduction over the universe U with respect to tests T is a map from a function f : U → {0, 1} to an oracle circuit HC(f ) : U → {0, 1} so that the following holds: if for every 2δ-dense measure µ over U , there's a function t ∈ T that (1/2 + ε)-approximates f over µ, then there exist k functions T 1 , ..., T k so that computing HC(f ) with oracle access to t 1 , ..., t k is a (1 -δ)-approximation of f over the uniform distribution.

We have the luxury of choosing 2δ as the density parameter, which is optimal, due to the more refined boosting-type argument of Holenstein [Hol05] in which Holenstein presents and explicit (ε, δ, O( 1 δε 2 )) hardcore lemma reduction.

Theorem 31 ([Imp19], informal). If there's a (ε, δ, k)-black-box hardcore lemma reduction over {0, 1} n for tests T , then there's a (ε , δ , εδ, k)-black-box dense model reduction over {0, 1} n for tests T .

In order to state our results more explicitly, we'll need a slightly refined notion of black-box hardcore lemma. Namely, fix a ground distribution ρ over U . Define the density of a measure µ : U → [0, 1] relative to ρ as the weighted sum d ρ (µ) = E x∼ρ [µ(x)]. Similarly, the distribution induced by µ over the ground distribution ρ is given by the mass function p(x) = ρ(x)µ(x) dρ(µ) . A black-box hardcore lemma relative to ρ is then a black-box translation from (1/2 + ε)-approximations of f for any µ with d ρ (µ) ≥ 2δ into a (1 -δ)-approximation of f over ρ.

Consider a set D : U → [0, 1] which is distinguishable by T from every dense measure over U . We want to exhibit find a function that refutes D's pseudo-density.

The most obvious approach is to use D's characteristic function, which could be a somewhat easy function for T , as T distinguishes D. Applying this directly, could be a problem: suppose µ is a set of size δ 0 |U | and D is a subset of size |µ|/3. Then the characteristic function of µ distinguishes between D and µ with advantage 2/3. But since D is small inside of µ, the probability that 1 µ = D with inputs drawn from µ is 1/3.

To fix this, we want to build a new universe U out of U that contains a blown-up copy of D, so as to build a function f which encodes D that is relatively unbiased. Specifically, consider a new universe U = {(x, 1) : x ∈ D} ∪ {(x, -1) : x ∈ U }.

The ρ-mixture distribution on U is defined as follows: with probability ρ, sample x from D and output (x, 1) and with probability 1 -ρ, sample x from U and output (x, -1). For a class T of tests over U , we'll extended each T ∈ T to a function over U as T (x, b) = T (x). Now we can explicitly state the theorem: Theorem 32. Let T be a class of tests over U containing the constants and closed under negation and suppose HC is an (ε, δ -λ)-hardcore lemma over the ρ-mixture distribution on U with respect to T (extending T to U as above). Then there's a (ε , δ , γ)-dense model theorem over T with ε = O(ε + λ/δ), δ = λ 1-δ , and γ = δ 1-δ whenever δ ≤ 2ελ + λ/δ -2ελ 2 /δ. For completeneess, we'll reproduce the proof from [Imp19] in the Appendix. This reduction allows us to readily conclude the following: Corollary 33. Any (ε, δ)-black-box hardcore set lemma reduction HC requires majority. Specifically, if HC is an (ε, δ-λ)-black-box hardcore setlemma reduction, then there's an AC 0 circuit of size poly( δ η 3 γ 2 ) and oracle access to HC computing majority on 1/η bits where δ = λ 1-δ , γ = δ 1-δ and η = ε + δ γ + log(1/δ ) 2(n-1) . [LTW11] had previously observed an exponential AC 0 [⊕] lower bound on HC by observing that HC can be used to approximate majority. This result is slightly different, as it gives an AC 0 Turing reduction from majority to any proof of the hard-core lemma (which in turn implies exponential AC 0 [⊕] lower bounds, see below). Since the hardcore lemma can be used to prove a hardness amplification result, it can also be deduced as a corollary of the Shaltiel-Viola lower bound [SV10].