Constructing explicit pseudorandom generators (PRGs) for interesting classes of Booleanvalued functions is a fundamental problem in complexity theory which has witnessed a rich line of work. An important class of functions, which have been intensively studied from this perspective, are linear threshold functions (henceforth referred to as LTFs), i.e. functions of the form f (x) = sign( n i=1 w i x i -θ) for some w ∈ R n and θ ∈ R. LTFs arise naturally in a variety of areas including machine learning, social choice theory, circuit complexity and pseudorandomness. Through a very successful line of work [8,26,13], explicit PRGs have been obtained which ε-fool the class of LTFs over {-1, 1} n with seed length O(log n + log 2 (1/ε)) [26], or alternately seed length O(log(n/ε)(log log(n/ε)) 2 ) [13]. For LTFs over the Gaussian distribution, [23] give an ε-PRG that fools LTFs with seed length O(log n + log(1/ε) log log(1/ε))).
Given these successes in designing PRGs to fool a single LTF, a natural next goal is to develop PRGs for intersections of k LTFs (i.e. polytopes with k facets) or, more generally, for arbitrary Boolean functions of k LTFs. PRGs for polytopes have direct applications to central problems at the intersection of derandomization and combinatorial optimization, such as deterministic approximate volume estimation for polytopes and approximate counting of feasible solutions to 0-1 integer programs. The standard way to use a PRG for such applications is to run through the list of all seeds, and hence it is desirable to have seed length as small as possible as a joint function of n and k. In particular, a seed length of the form O(log n) • α(k, 1/ε) leads to a running time of n O(α(k,1/ε)) , which even for constant ε is super-polynomial for any super-constant k. In contrast, a seed length of the form O(log n) + α(k, 1/ε) leads to a running time of poly(n) • 2 α(k,1/ε) , which can be a fixed polynomial in n even for various super-constant values of k (depending on the function α).
In this paper we work over Gaussian space, and we give the first PRGs for intersections and arbitrary functions of k LTFs which have seed length of the form O(log n) + α(k, 1/ε) for all k. For intersections of LTFs we achieve α(k, 1/ε) = poly(log k, 1/ε), and for arbitrary functions of LTFs we achieve α(k, 1/ε) = poly(k, 1/ε). Thus for constant ε our seed length is O(log n) for k = 2 (log n) c LTFs (for intersections) and k = (log n) c LTFs (for arbitrary functions), where c > 0 is an absolute constant. Previously, such an O(log n) seed length was only known for k = O(log(n)/ log log n) (for intersections) and k = O(log log n) (for arbitrary functions) [14]. Thus, in both cases our PRGs achieve the (optimal) O(log n) seed length for exponentially larger values of k than was previously known.
Before stating our results in detail we recall the definition of a PRG over Gaussian space (see [18,17,16,19,23,21]):
Definition 1 (PRGs for Boolean-valued functions over Gaussian space). Let C be a class of functions from R n to {-1, 1}. Given ε > 0, a function G : {-1, 1} s → R n is an ε-PRG for class C over Gaussian space if for every function where G (n) denotes (G 1 , . . . , G n ), a random variable distributed according to the standard Gaussian N (0, 1) n , and U (s) denotes the uniform distribution on {-1, 1} s . The parameter s is called the seed length of G.
Our PRG results. The following are our main PRG theorems:
Theorem 2 (Fooling arbitrary functions of LTFs). There is an explicit PRG which ε-fools any Boolean function of k LTFs g(h 1 , . . . , h k ) over N (0, 1) n , for any ε > 0 and any k, with seed length
This seed length is not far from the best possible in terms of its dependence on both n and k, as it is not difficult (see Appendix A) to establish a seed length lower bound for this class of max{ log n , k} = Ω(k + log n) for any 1 ≤ k ≤ n.
In the special case when the combining function g is an AND, we get an exponential improvement in the seed length dependence on k:foot_0 Theorem 3 (Fooling intersections of LTFs). There is an explicit PRG which ε-fools any intersection of k LTFs over N (0, 1) n , for any ε > 0 and any k, with seed length O (log n + poly(log k, 1/ε)) .
Here too the seed length is not far from best possible for a broad range of parameters; we note that the above-mentioned lower bound of log n even when k = 1 implies a seed length lower bound of Ω(log n), which is Ω(log n + log k) for any k ≤ poly(n) (the most interesting regime for Theorem 3).
For arbitrary functions of k LTFs, Theorem 2 is the first result which gives a seed length of O(log n) for k = (log n) c , and for intersections of k LTFs Theorem 3 is the first result which gives a seed length of O(log n) for k = 2 (log n) c . As mentioned earlier and discussed in more detail below, an optimal seed length of O(log n) was previously only known [14] for exponentially smaller values of k in both settings. Below we briefly review prior results on explicit PRGs for these classes, starting with intersections of LTFs.
The most directly comparable prior result for intersections of k LTFs is the main result of [28], which gives a PRG for intersections of k LTFs over {-1, 1} n with seed length log(n) • poly(log k, 1/ε). (Such a PRG directly implies a PRG for intersections of k LTFs over Gaussian space with the same seed length via a standard reduction.) The [28] PRG builds on a PRG due to Harsha et al. [16] which has seed length log(n) • poly(log k, 1/ε) for intersections of sufficiently regular LTFs; the [16] PRG in turn is similar to a PRG construction of Meka and Zuckerman [26] (for a single LTF) in which the basic idea is to (pseudorandomly) hash the coordinates into buckets and use -wise independence for coordinates hashed to the same bucket. The analysis of the [28] PRG combines a range of technical ingredients including an invariance principle for polytopes that [16] establish, combinatorial PRGs for depth-2 circuits, and new Littlewood-Offord type theorems for polytopes.
PRGs for intersection of LTFs were also studied by Gopalan, O'Donnell, Wu, and Zuckerman [14], Diakonikolas, Kane and Nelson [9], and recently by Servedio and Tan [29]. These results give PRGs with respect to the uniform distribution on the Boolean cube (in fact, the PRG in [14] fools arbitrary product distributions). For general k, the seed length of the PRG in [14] for intersection of k LTFs is O((log n + k log(k/ε)) • log(k/ε)). This linear dependence of the seed length on k is far from optimal; for example, if k ≥ n then their result does not yield a non-trivial PRG. For the special case when k/ε is at most poly(log n), [14] achieves the better seed length of O(log n + k log(k/ε)). Thus, for k = O(log n/ log log n), the [14] seed length is O(log n).
The work of Diakonikolas et al. [9] achieves a similar polynomial dependence on k in the seed length of their PRG (more precisely, they achieve seed length O(log n • poly(k, 1/ε)), and their PRG works also for intersections of k degree-2 polynomial threshold functions). The work of Servedio and Tan [29] achieves seed length with polylogarithmic dependence on k, but only gives a good bound against intersections of LTFs with small integer weights. In more detail, if each of the k LTFs in the intersection has all its weights w i being integers in [-t, t], then the PRG in [29] has seed length poly(log n, log k, t, 1/ε). The parameter t for an LTF can in general be exponential in n (and in fact, for a random LTF, t is exponential in n with high probability), and hence the [29] result is of interest only for intersections of low-weight LTFs.
Turning to arbitrary functions of k LTFs, we observe that (as indicated in the earlier footnote) any PRG for intersections of k LTFs can be used to fool arbitrary functions of k LTFs by setting its accuracy parameter to ε/2 k . If the seed length of the PRG has an inverse polynomial dependence on the accuracy parameter (as in our result) then this simple approach does not yield a very good seed length, but [14] used essentially this approach to obtain a PRG that fools any function of k LTFs with seed length O((
In the special case when k • 2 k /ε is at most poly(log n), they achieve a better seed length of
Our results on deterministic approximate counting. By combining our new PRGs with invariance principles and a (multi-)regularity lemma, we obtain deterministic algorithms which approximately count the number of satisfying assignments to intersections or arbitrary functions of k arbitrary LTFs over {-1, 1} n . (Note that such algorithms, unlike PRGs, are non-oblivious, i.e. they can "inspect" the particular LTFs which comprise the input to the problem.) Theorem 4 (Deterministic approximate counting for arbitrary functions of k LTFs over {-1, 1} n ). There is a deterministic algorithm which, given as input k LTFs h 1 , . . . , h k over {-1, 1} n , an explicit function g : {-1, 1} k → {-1, 1} and an error parameter ε > 0, runs in poly(n) • 2 poly(k,1/ε) time and outputs a value ṽ ∈ [0, 1] such that |ṽ -v| ≤ ε, where v is the fraction of points in {-1, 1} n that satisfy g(h 1 , . . . , h k ).
For intersections of LTFs, by combining our approach with the [28] PRG we can get an exponentially better runtime dependence on k: Theorem 5 (Deterministic approximate counting for intersections of k LTFs over {-1, 1} n ). There is a deterministic algorithm which, given as input k LTFs h 1 , . . . , h k over {-1, 1} n and an error parameter ε > 0, runs in poly(n) • 2 poly(log k,1/ε) time and outputs a value ṽ ∈ [0, 1] such that |ṽ -v| ≤ ε, where v is the fraction of points in {-1, 1} n that satisfy
We are not aware of prior results on deterministic approximate counting for intersections (or arbitrary functions) of k LTFs which run faster than simply enumerating over the seeds of a PRG. Thus Theorem 4 gives the first deterministic algorithm that runs in fixed poly(n) runtime even for k which is polylogarithmic in n; as indicated earlier, given the previous state of the art on PRGs for arbitrary functions of k LTFs for k = ω(log log n) prior algorithms would have a running time of at least n poly(k) . Similarly, Theorem 5 gives the first deterministic algorithm that runs in fixed poly(n) runtime even for k = 2 (log n) Ω(1) . The previous state of the art on PRGs for intersection of k LTFs for k = ω(log n/ log log n) would have a running time of at least n poly(log k) (such a running time is obtained simply by enumerating over the seeds of the [28] PRG).
A key ingredient in the proof of Theorem 4 is an invariance principle for arbitrary functions of k LTFs, analogous to the main structural result of [16] which is an invariance principle for intersections of k LTFs. Such an invariance principle was proved in [14], and we provide an alternate proof in Appendix C (which is very different from the proofs of the invariance principles in [16,14]). We believe this could be of independent interest. We elaborate on this, still at a conceptual level, in Section 3 and give full details in Section 7.
A straightforward approach to Theorem 5 using only the multi-regularity lemma and an invariance principle would have a running time which is exponential in k because the number of leaves in the decision tree constructed by the multi-regularity lemma is exponential in k. We achieve a quasi-polynomial dependence on k by exploiting additional structure in the decision tree (specifically, that it is a so-called "junta decision tree" in which the same variable occurs at each node of any given depth). Intuitively, this makes it possible for us to use the [28] PRG on the space of all variables occurring in the decision tree (to "pseudorandomly sample" leaves of the decision tree and use only those to construct an accurate estimate of the overall desired probability). Since the size of this variable space, roughly speaking, is m = Õ(k) (crucially with no dependence on n), the [28] PRG's seed length in this context (of intersections of k LTFs over m variables) is log(m) • poly(log k, 1/ε) = poly(log k, 1/ε), which leads to our overall final running time of poly(n) • 2 poly(log k,1/ε) .
We use the same simple PRG construction to obtain both of our PRG results (Theorems 2 and 3); the two results are obtained by instantiating the parameters in two different ways.
We describe this PRG below with general parameters; the precise parameter settings we use for each class (intersections versus arbitrary functions of k LTFs) will be made clear in the course of the respective analyses. An idealized version of our PRG is as follows: 1. Let G (d) be an N (0, 1)
d Gaussian (which we view as a column vector).
Let A ∈ R d×n be a pseudorandom Johnson-Lindenstrauss matrix drawn from the distribution of pseudorandom d × n JL-matrices given by the work of Kane, Meka and Nelson [20] (more details on this will be given below).
The actual PRG differs from the above-described idealized version because using finitely many bits it is not possible to generate a draw from the continuous G (d) distribution with perfect fidelity. So in Step 1 the actual PRG uses a discrete approximation of each coordinate of G (d) (we explain precisely what is meant by this in Appendix B); let Ĝ(d) denote the resulting distribution over R d . For clarity of exposition, the main analysis in the paper will be carried out for a "perfect" Gaussian G (d) , i.e. we will analyze the idealized PRG and show that it is an O(ε)-PRG for each of our two classes of interest (intersections and arbitrary functions of k LTFs). Appendix B shows that, for each of these two classes, if the idealized generator (which uses G (d) ) is an O(ε)-PRG, then so is the actual generator which uses Ĝ(d) .
C C C 2 0 1 9 4:6
High level idea of our generator. The Johnson-Lindenstrauss (JL) transform is one of the most important tools in high-dimensional data analysis. In a nutshell, for any error parameter ε, the JL transform gives a family D of d × n matrices such that for A ∼ D and any k unit vectors W 1 , . . . , W k ∈ R n , with high probability, the following holds: For all 0 ≤ i, j ≤ k, AW i -AW j 2 = (1 ± ε) W i -W j 2 (where W 0 = 0). Crucially, one can obtain this guarantee with d = O(ε -2 log k).
We can reinterpret the guarantee of the JL transform in the following way: Let A ∼ D and consider the two distributions Z := A T • G (d) and Z = G (n) . Let W ∈ R k×n be the k × n matrix whose rows are W 1 , . . . , W k . Then, for any θ, the distributions X = W • Z -θ and Y = W • Z -θ (i) are both Gaussian distributions over R k , (ii) have the same mean, and (iii) are such that the two k × k covariance matrices Cov(X) and Cov(Y) differ pointwise by at most ε. Let us define the affine function f : R n → R k as f (z) = W z -θ. Then, the guarantee of the JL transform is that Cov(f (Z)) ≈ ε Cov(f (Z )); we may loosely view this guarantee as showing that the generator above fools the covariance.
The above perspective leads to the insight which motivates our work, which is essentially the following: since both X and Y are Gaussians, which are completely determined by their means and covariances, other interesting tests besides the covariance may reasonably be expected to be fooled by (a pseudorandom version of) the Johnson-Lindenstrauss transform. In this paper we consider tests of the form h(sign(f (z) 1 ), . . . , sign(f (z) k )), where h may be any function from {-1, 1} k to {-1, 1} (we will also specialize to the case where h is an AND) and f (z) i denotes the i th coordinate of f (z). In other words, we are interested in fooling functions (given by h) of k LTFs (given by sign(f (z) 1 ), . . . , sign(f (z) k )). As we show in this paper, for a suitable choice of d (depending on whether h is arbitrary or is an AND) our generator can indeed fool all functions of the above form.
Seed length of our PRG. In order to state the seed length of our generator we first need to identify all of the relevant parameters. In Step 1, for each of our two results we will take d = O(log(k/δ )/ε 2 ) where ε is a parameter that will be discussed below; as mentioned above each coordinate of Ĝ(d) will be a discrete approximation of an N (0, 1) Gaussian. In
Step 2, the KMN distribution over pseudorandom d × n JL-matrices has two additional parameters, which we denote ε and δ (see Section 4.2 for details.)
For the first step, as we show in Appendix B, a total of O(d log(kd/ε)) many random bits suffice to generate a draw from Ĝ(d) . For the second step, as we discuss in Section 4.2, a pseudorandom d × n JL-matrix with parameters ε , δ can be drawn from the KMN distribution using O(log n + log(1/δ ) • log(log(1/δ )/ε )) bits of randomness. So the overall seed length of our PRG is
As we will see in Section 4.2, we will always take δ to be ε, so the seed length of our generator is
(1)
We will instantiate the parameter ε to one specific value (a function of k and ε) in Section 5 for arbitrary functions of LTFs, and to another specific value in Section 6 for intersections of LTFs, thus obtaining the seed lengths claimed in Theorems 2 and 3.
In the rest of this section we give an overview of the analyses of our PRGs. While the same PRG gives both our results, the analyses are quite different for the two classes we consider (arbitrary functions of LTFs and intersections of LTFs). We first sketch the (simpler) analysis for fooling arbitrary functions of LTFs.
We start by recalling some definitions which are useful for our overview. An
Given two random variables X, Y over R k , the quadratic Wasserstein distance W 2 (X, Y) between X and Y is defined to be
where the infimum is taken over all couplings ( X, Y) of X and Y. 2Now we can present our overview. Our goal is to show that our PRG ε-fools every function of the form g(h 1 (x), . . . , h k (x)) : R n → {-1, 1}, where g : {-1, 1} k → {-1, 1} is arbitrary and each h i : R n → {-1, 1} is an LTF, relative to the standard Gaussian distribution. This is equivalent to showing the following: for any unit vectors W 1 , . . . , W k ∈ R n and any θ = (θ 1 , . . . , θ k ) ∈ R k , taking W to be the k × n matrix whose rows are W 1 , . . . , W k and taking O to be any union of orthants over R k , we have
Here is a high-level sketch of why our PRG ensures this.
(1) A (pseudorandom) JL projection of the k unit vectors W 1 , . . . , W k ∈ R n results in much lower-dimensional vectors V 1 , . . . , V k ∈ R d , where d = Θ(log(k)/ε 2 ), which approximately preserve pairwise distances. Let us write Σ W (Σ V respectively) to denote the k × k covariance matrix of the k-dimensional Gaussian random variable W G (n) -θ (V G (d) -θ respectively, where G (d) is distributed according to N (0, 1) d ). As we will see in Section 4.1, we have that Σ W and Σ V are entrywise close to each other (see Observation 6 for details).
(2) The entrywise closeness of Σ W and Σ V implies that the quadratic Wasserstein distance
(See Proposition 8 in Section 5.2 for details.) (3) As the main step of our analysis, using an adaptation of an argument from [5], in Section 5.3 we use (3) to infer that for every union of orthants O, we have
This concludes the analysis since the inequality (4) is exactly the same as (2). This is because for each j we have V j = W j A T where A is the (pseudorandom) projection matrix.
At a high level, our analysis for fooling intersections of LTFs exploits the rich and influential line of work on analyzing supremum (maximum) of Gaussian processes [24,11,31]. We recall that a Gaussian process is a set of jointly normal random variables (the set may be infinite, though we will only concerned with the finite case where it has cardinality k). To see the relationship between the maximum of a Gaussian process and an intersection of LTFs, let W 1 , . . . , W k ∈ R n be unit vectors and θ ∈ R k . Define the LTF h i (z) = sign(W i z -θ i ) and consider the k-face polytope h 1 (z) ∧ . . . ∧ h k (z). Showing that our PRG ε-fools this k-face polytope (i.e., the function h 1 ∧ . . . ∧ h k ) relative to the standard Gaussian distribution is equivalent to showing the following: Taking W to be the k × n matrix whose rows are
Both {(W Z) j -θ j } 1≤j≤k and {(W G) j -θ j } 1≤j≤k are Gaussian processes, and we are interested in comparing the maxima of these two processes. If we were interested in comparing just the expectations of the maxima, i.e., E[max j∈ [k]
then the classical Sudakov-Fernique inequality [11,30] provides a tool to compare (and prove the closeness of) these two quantities. Indeed, Meka [25] used this as a starting point in his work on a deterministic algorithm for estimating the supremum of a Gaussian process. We are interested in a somewhat more delicate quantity, and so we will use a generalization of a recent result of Chernozhukov et al. [6] which itself extends the Sudakov-Fernique inequality. Now we turn from the above conceptual overview to a more detailed sketch of our analysis. Let the vectors V 1 , . . . , V k and the covariance matrix Σ V be defined in the previous subsection.
(1') The first step of the argument is identical to Step 1 in the previous subsection: the covariance matrices Σ W and Σ V are entrywise close to each other. (2') Next, we use the entrywise closeness of Σ W and Σ V to show that for any sufficiently smooth function g, we have that
is small. This is via an extension (to non-centered Gaussians) of Theorem 1 of [6], which in turn is a generalization of Chatterjee's quantitative Fernique-Sudakov bound [4]. 3We carry out this step in Section 6.2. (3') Using a result of [16] (which follows almost directly from an influential work of Nazarov [27]), we have that the real-valued random variable max
which is a max of non-centered Gaussians, has good anticoncentration, meaning that it does not put very much mass in any small interval. See Section 6.3 for more details.
(4') We specialize (6) to the case where g is a smooth approximator of the sign function. For a particular such g, combining (6) with the anticoncentration of max j∈
mentioned above, we can pass from g, which is a smooth approximator of sign(•), to the actual sign(•) function, and thereby show that
is small. We give this argument in Section 6.4. (5') Having (7) be small is exactly the same as having the LHS of ( 5) is small, since for each j we have V j = W j A T where A is the (pseudorandom) projection matrix from Step 1 of our PRG. See Section 6.5 for more details.
In this section, we give an overview of our approximate counting algorithms for intersections and arbitrary functions of LTFs. We begin with the description for arbitrary functions as it relies on (extensions of) relatively well known tools from the literature such as regularity lemmas and invariance principles. In particular, we follow the (by now standard) paradigm of reducing the counting problem over the discrete cube to the Gaussian case by applying an appropriate regularity lemma; the proof of correctness relies on an invariance principle for arbitrary functions of LTFs. Once in the Gaussian case, we apply Theorem 3 which allows us to do counting over Gaussian space. This is explained in more detail in Section 3.1.
We then move on to the case of intersections of LTFs, which is somewhat more subtle. Similar to the first case, we also use a regularity lemma to reduce the Boolean case to the Gaussian case. However, instead of a naive approach of traversing all the root-to-leaf paths in the decision tree (constructed by the regularity lemma), we use the PRG construction of [28] to traverse only a small subset of the leaves. More details are given in Section 3.2.
A regular LTF is an LTF sign( n i=1 w i x i -θ) in which, intuitively, no individual weight w i has large magnitude compared to the overall magnitude of the weights (see Section 7.1 for a precise definition). The main structural result of [16] is an invariance principle for intersections of LTFs: roughly speaking, this states that if
LTFs all of which are sufficiently regular, then the expected values of F 0 (U (n) ) (where the input is uniform over {-1, 1} n ) and of F 0 (G (n) ) (where the input is a standard N (0, 1) n Gaussian) are close. A notable aspect of the [16] invariance principle is that its error bound has only a poly-logarithmic dependence on k (see Theorem 28 in Section 7.3 for a precise statement). Now, consider any
arbitrary). A naive approach based on just using the [16] invariance principle 2 k times together with a union bound would give an invariance principle for arbitrary functions of k LTFs with an error bound that depends exponentially on k. Instead, we use an analogue of the [16] invariance principle which goes beyond intersections of LTFs and works for arbitrary functions of k LTFs. The work of Gopalan et al. [14] gives an invariance principle for arbitrary functions of k LTFs that has a polynomial dependence on k in the error bound. We provide an alternate proof of this invariance principle for arbitrary functions of k LTFs. This polynomial dependence on k is crucial for obtaining a final overall running time for counting satisfying assignments with a singly exponential dependence on k, rather than a doubly exponential dependence which would follow from the naive approach.
As we explain in Section 7.2, the proof of our invariance principle is completely different from the proofs of of [16], [14]; we feel that our new proof of the invariance principle, Theorem 24, may be of independent interest. The [16] and [14] invariance principles are proved using a Lindeberg-type "replacement" argument; key ingredients are an analysis of hashing n coordinates into buckets and bounds on the derivatives of particular "smooth mollifiers" for functions of LTFs. Our proof of Theorem 24 uses none of these ingredients; instead, its main components are (a) a CLT for Wasserstein distance due to Valiant and Valiant [32], and (b) a conversion from Wasserstein distance to "union-of-orthants" distance. (Indeed, the ideas underlying the proof of Theorem 24 are very similar to the ideas underlying our PRG for arbitrary functions of k LTFs; this is analogous, at a high level, to how the proof of the [16] invariance principle is closely related to the analysis of the [16] PRG for intersections of regular LTFs.)
Using the invariance principle for deterministic approximate counting. By combining the invariance principle for arbitrary functions of LTFs with our PRG, which shows that a random variable Z ← Gen is such that the expectation of F (Z) is close to that of F (G (n) ), it is straightforward to obtain a deterministic approximate counting algorithm for arbitrary functions of k regular LTFs over {-1, 1} n simply by enumerating over all the seeds of our PRG. This algorithm has running time poly(n) • 2 poly(k,1/ε) .) To obtain a deterministic approximate counting algorithm for arbitrary functions of k general LTFs over {-1, 1} n , we combine the above algorithm with the deterministic algorithmic version of the multi-regularity lemma of [14]. Briefly, this is a deterministic algorithm which builds a decision tree of depth roughly k, with the property that at almost every leaf ρ of the decision tree, either the restriction of g(h 1 , • • • , h k ) according to ρ is very close to a constant function -1 or 1, or else each restricted LTF h 1 ρ, . . . h k ρ is regular (and hence the deterministic approximate counting algorithm for arbitrary functions of regular LTFs can be used). We note that the total number of leaves in this decision tree is exponential in k. By running the approximate counting algorithm for functions of k-regular LTFs at each of the leaves, it is possible to approximate the overall number of satisfying assignments. We give the details of this (fairly standard) approach in Section 7.2.
Recall that the invariance principle of [16] shows that if all the LTFs are sufficiently regular, then the expected values of F 0 (U (n) ) and of F 0 (G (n) ) are close, where crucially the error bound only has a polylogarithmic dependence on k. By combining this with our PRG, it is straightforward to obtain a deterministic approximate counting algorithm for intersections of k regular LTFs over {-1, 1} n simply by enumerating over all the seeds of our PRG -the resulting running time is poly(n) • 2 poly(log k,1/ε) . For intersections of general halfspaces, one can apply the multi-regularity lemma of [15] to reduce to the case of intersection of regular halfspaces. A naive application of this (similar to the previous subsection) will result in a running time exponential in k -this is because there are 2 k leaves in the resulting decision tree and running the algorithm for each of the leaves separately will result in an exponential in k overhead.
To instead get a 2 poly(log k) overhead, we crucially rely on two facts: (i) the decision tree constructed by the regularity lemma is non-adaptive, i.e., all nodes at the same level are labeled by the same variable. Further, if the set of internal variables is denoted by S, then this set can be enumerated in time poly(S). (ii) For any fixing of the set of variables in S, the computation of the decision tree can be represented as an intersection of k halfspaces.
Glossing over some subtleties, this suggests that instead of doing approximate counting for all the leaves in the decision tree, one can just perform this computation on a subset of the leaves given by the output of a PRG. In particular, we use the PRG due to [28] to select the subset. While the PRG in [28] has a (log n) • poly(log k) seed length (where n is the ambient dimension), in this application 'n' is set to |S| which has polynomial dependence on k (for constant error ε > 0). Putting this together, we obtain a deterministic algorithm for counting intersection of k arbitrary halfspaces with running time poly(n) • 2 poly(log k,1/ε) . The full details are given in Section 7.3.
We write W ∈ R k×n to denote the matrix whose j-th row is the weight vector of the j-th LTF in a function of k LTFs. We assume that each such LTF has been normalized so that its weight vector has norm 1. For j ∈ [k] (indexing one of the LTFs) we write W j = (W j 1 , . . . , W j n ) to denote the j-th row of W , so W j = 1 for all j. Thus an arbitrary function of k LTFs is g(h 1 , . . . , h k ), where g : {-1, 1} k → {-1, 1} and
where
(we take -1 to represent True and 1 to represent False throughout), and an intersection of k LTFs is a function
Throughout this paper we will use notation like θ to denote vectors in R k , i.e. θ = (θ 1 , . . . , θ k ) ∈ R k . We write G or simply G (n) to denote (G 1 , . . . , G n ), a random variable distributed according to N (0, 1) n (so each of G 1 , . . . , G n is an i.i.d. N (0, 1) Gaussian).
As above let W ∈ R k×n have j-th row W j with W j = 1 for all j ∈ [k]. For convenience we also define W 0 ∈ R n to be the all-0 vector. Let d = O(log(k/δ )/ε 2 ) (where ε will be taken to be at most 1) and let V ∈ R k×d satisfy the following:
where we take V 0 = (0, . . . , 0) ∈ R d . (As we will see in the next subsection, V 1 , . . . , V k should be thought of as the vectors we get by doing a pseudorandom JL-projection of W 1 , . . . , W k to d dimensions.)
We will consider the two k-dimensional Gaussian random vectors W G (n) and V G (d) . The covariance matrix of W G (n) , which we denote Σ W , is the k × k matrix W T W which has σ W ij := W i • W j as its (i, j) entry, and similarly the covariance matrix
the maximum entry-wise difference between the two covariance matrices. The following simple observation upper bounds ∆:
C C C 2 0 1 9
PRGs from Gaussian Processes Proof. Taking i = 0, (8) implies that each
and similarly (using the fact that each
which implies
where for the penultimate inequality we used W i -W j 2 ≤ 4 and ε 2 ≤ ε which holds since 0 < ε < 1.
Recall that Steps 1 and 1 of the analysis are identical for arbitrary functions of LTFs (in Section 2.1) and for intersections of LTFs (in Section 2.2). We give the details of this step here.
We use the following derandomized JL lemma given by Kane, Meka, and Nelson [20]:
Theorem 7 (Derandomized Johnson-Lindenstrauss [20]). Let 0 ≤ ε , δ < 1/2 and let δ = δ /k 2 . There is a distribution D over random matrices A ∈ R d×n , d = O(log(k/δ )/ε 2 ), such that (i) a draw of A ← D can be generated using O(log n+log(1/δ )•log((log(1/δ ))/ε )) bits, and (ii) the following holds: Fix unit vectors W 1 , . . . , W k ∈ R n . Then
Let V j = W j A T where A ← D. By Theorem 7, except with failure probability at most δ , (8) is satisfied. We will always take δ = ε, and so this δ failure probability just gets absorbed into the overall O(ε) error bound of the PRG. Fix V 1 , . . . , V k to be any such outcome of V 1 , . . . , V k ; in the rest of the argument we will work with this V 1 , . . . , V k . Note that by Observation 6 we have that ∆, which is defined in terms of this V 1 , . . . , V k , satisfies ∆ ≤ 9ε .
Fooling arbitrary functions of LTFs: Proof of Theorem 2
As will be seen in the analysis below, in order for the overall PRG to O(ε)-fool arbitrary functions of k LTFs, we take ε = ε 6 k 15/2 . Recalling that δ = ε, by (1) the overall seed length (as a function of n, k and ε) is O(log n) + Õ( k 15 ε 12 ), as claimed in Theorem 2. In the rest of this section we establish correctness of the PRG.
Recall that the quadratic Wasserstein distance between random variables X, Y in R k is defined to be
where the infimum is taken over all couplings ( X, Y) of X and Y. (8) and let θ ∈ R k . Then we have
where τ = O(k
Proof. Observe that W G (n) -θ and V G (d) -θ have the same mean. For this case, Proposition 7 of Givens and Shortt [12] shows that
Here Σ W and Σ V are the covariance matrices of the distribution W G (n) -θ and V G (d) -θ respectively 4 . To bound the expression on the right hand side, first observe that
The last inequality uses Observation 6. To proceed further, we recall the following very useful fact from Bhatia [2] (Theorem X.1.3) Fact 9. Let • be any unitarily invariant matrix norm. For psd matrices A and B, we have the following
where |X| denotes the psd matrix √ X * X.
For any symmetric matrix X, let X tr denotes its trace norm, i.e., the sum of the singular values of X. Note that the trace-norm is unitarily invariant. With this, we now have
In the above, the first inequality uses the fact that for any symmetric matrix X, |Tr(X)| ≤ X tr and the second inequality follows from Fact 9. We now recall the following fact:
4 [12] states their theorem for non-singular Σ V and Σ W . However, we can always perturb our Gaussians infinitesimally, apply (13) and then take a limit. 16)
The second equality simply uses that for symmetric X, |X| tr = X tr . Next, we recall the following useful inequality for unitarily invariant norms (see [2], p.94).
Applying Fact 11 to the right hand side of ( 16), we obtain
Now, Σ W is a matrix in which each entry W i • W j is upper bounded by 1 in absolute value.
Here the last inequality is again using Observation 6. Combining this with (17), we have
Combining the above equation with ( 14) and (13) (and using triangle inequality), we get that
This immediately yields the proposition.
The following definition will be convenient: Given two random variables X, Y over R k , the union-of-orthants distance between X and Y is defined to be
where the max is taken over all 2 2 k possible unions of orthants O in R k . This definition aligns well with arbitrary functions of k LTFs g(h 1 , . . . , h k ) because of the following easy observation:
Observation 12. For any g : {-1, 1}
where τ is as defined in Proposition 8.
The argument here is similar to the proof of Theorem 5 in [5]. That result used a CLT due to Valiant and Valiant (which gave an upper bound on the L 1 (as opposed to quadratic, i.e. W 2 ) transportation distance between a certain sum of vector-valued random variables and a Gaussian distribution) to obtain an upper bound on union-of-orthants distance between those two distributions. We briefly explain the main idea (which is quite simple) behind the argument in our setting.
We consider an optimal coupling of the random variables X = W G (n) -θ and Y = V G (d) -θ which achieves the minimal quadratic transportation distance as in (11). Since by Proposition 8 the quadratic transportation cost W 2 (X, Y) of transforming X to Y is "small", the optimal coupling cannot move a "non-small" amount of mass by a distance that is not "small." Assume (contrary to our desired conclusion) that the union-of-orthants distance between X and Y is not small, and fix a union of orthants O that achieves the max in (18). Without loss of generality we may suppose that X puts more mass on O than Y (and this difference is large by the above assumption). Gaussian anticoncentration tells us that X can only have a small amount of mass overall that is close to orthant boundaries, and hence X can have only a small amount of such mass in O. This means that a non-small amount of mass from X must be moved a non-small distance (since it must go from being within O and not close to any orthant boundary, to being outside of O) in order to transform X to Y; but this contradicts the premise that W 2 (X, Y) is small.
We now proceed to the formal argument.
Proof of Lemma 13. As above let X = W G (n) -θ and Y = V G (d) -θ. By Proposition 8 we have that W 2 (X, Y) ≤ τ. We define
to be the region of all points in R k whose L ∞ -distance from any orthant boundary point is at most r. With foresight we choose r = τ 2/3 /k 1/3 (the rationale for this choice will be evident toward the end of the proof). We partition O into O bd := O ∩ B r (the points in O that lie close to the orthant boundaries) and O in := O \ B r (the points in O that lie far away from the orthant boundaries). We have
We bound the quantities Ξ and Γ separately.
For Γ, we have that
where we used the fact that each coordinate X i of X is a one-dimensional Gaussian with variance
C C C 2 0 1 9 4:16
For Ξ, let us assume without loss of generality (a symmetrical argument works in the other case) that Pr
so D is the joint distribution of a pair (U, V) of R k -valued random variables with marginals distributed according to X and Y respectively. Since
Next we define the quantities
We consider two cases, depending on the relative magnitudes of Ξ near (D) and Ξ far (D). If Ξ far (D) ≥ Ξ near (D), then we have
and hence Ξ ≤ 8τ 2 /r 2 , which along with our upper bound on Γ given by ( 20) completes the proof. If on the other hand Ξ near (D) > Ξ far (D), then
and again our upper bound on Γ completes the proof.
Observing that by our setting of parameters we have that k 2/3 τ 2/3 = O(ε), we get that (8). Recalling from Section 4.2 that all but a δ = ε fraction of outcomes V 1 , . . . , V k of V j = W j A T satisfy (8), we have
and recalling that a draw Z from our generator Gen is Z = A T G (d) , this is equivalent to
and the proof of Theorem 2 is complete.
Fooling intersections of LTFs: Proof of Theorem 3
As we will see in the analysis given below, in order for the overall PRG to ε-fool k-facet Gaussian polytopes it suffices to take ε = O(ε 3 / log 2 k) and δ = ε /k 2 , so by (1) the overall seed length (as a function of n, k and ε) is O(log n) + Õ( log 6 k ε 6 ) as claimed in Theorem 3. The following notation will be useful: For 0 < λ, k ≥ 1, and
We recall that the Kolmogorov distance between two real-valued random variables S and T is defined to be
For f : R k → R a smooth function we write ∂ j f (z) to denote ∂f ∂zj (z) and write
A crucial ingredient in executing step (2 ) of our analysis is the the following "soft-max" function which is used in [4,6] and many other works. The soft-max function F β : R k → R is defined as
For conciseness let us write e β to denote β -1 ln k. We record some useful facts about the soft-max function: Fact 14. For any vector v ∈ R k , and any parameter β > 0,
C C C 2 0 1 9
PRGs from Gaussian Processes Fact 15 (Lemma 3 of [6]). For every 1 ≤ i, j ≤ k, we have
where
Furthermore, we have
Fact 16 (Lemma 4 of [6]). Let m(z) = g(F β (z)) where g ∈ C 2 (R). Then for every 1 ≤ i, j ≤ k, we have
where π i and w ij are defined as in Fact 15 above. Fact 14 follows almost directly from the definition of F β . Facts 15 and 16 can be routinely verified by calculus.
The following is the main result of this section (cf. ( 6)):
Then for any β > 0, we have
Further,
We use the rest of this subsection to prove Theorem 17. The proof extends the proofs of similar results in [4,6] to the case of non-centered Gaussians. For ease of presentation, for i ∈ [k] define the non-centered Gaussian random variables
We may suppose, without loss of generality, that X = (X 1 , . . . , X k ) and Y = (Y 1 , . . . , Y k ) are defined over the same probability space and that X and Y are independent of each other. Our goal is to bound the magnitude of the difference
and let X i = X i -µ i be the centered version of X i and similarly let Y i = Y i -µ i . Observe that by independence we have E[X i Y j ] = 0 for all i, j ∈ [k]. Now, as is standard, we do a Slepian interpolation; so for t ∈ [0, 1], we define
and we write Z t to denote (Z t,1 , . . . , Z t,k ). We define the function
and we observe that
Thus to upper bound the magnitude of ( 22) it suffices to upper bound
. By applying the chain rule, we have
Now we recall the following "integration by parts" lemma, which is sometimes referred to as "Stein's identity:" Lemma 18 (Lemma 2 of [6], see also Lemma 2.1 of [4]). Let A = (A 1 , . . . , A p ) be a p-dimensional Gaussian random vector with mean zero and let f :
Observe that with this setting, ∂ k+1 f (A) = 0. Applying Lemma 18 with = k + 1, we get that
where the second equality uses the independence between X and Y. We get that
where ∆ = max i,j∈ [k] |σ W i,j -σ V i,j | is the quantity defined in (9). Thus, we are left with the task of upper bounding the double derivatives. We have
C C C 2 0 1 9 4:20
Applying Facts 15 and 16, it follows that
Hence combining ( 23), (24), and the above, and recalling that ∆ ≤ 9ε (see Observation 6), we get that
giving the first claim of the theorem. For the second claim, using Fact 14, it follows that
The second claim of the theorem now follows by setting β = (ln k)/ε .
We recall the following anticoncentration result from [16], which follows almost directly from a result of Nazarov [27]:
Lemma 19 (Lemma 3.4 of [16]: anticoncentration of multidimensional Gaussian). Let W 1 , . . . , W k be unit vectors in R n . For all θ ∈ R k and all λ > 0, we have
This can be viewed as a k-dimensional analogue of Theorem 3 from [6], which gives an anticoncentration bound on max{W 1 • G, • • • W k • G} (and also the above lemma is for non-centered Gaussians, whereas Theorem 3 of [6] is about centered Gaussians). As an immediate consequence of Lemma 19 we obtain the following: Theorem 20 (anticoncentration of max of non-centered Gaussians). Fix any θ ∈ R k . For all λ > 0 and all t ∈ R it holds that
In this section we prove the following theorem, which upper bounds the Kolmogorov distance between the random variables max j∈ (8). For all θ ∈ R k , the following bound holds:
This is equivalent to showing that for all θ ∈ R k and all t ∈ R, we have
Our argument follows the proof of Theorem 2 in [6]; the main idea is to combine Theorem 17, where g is a smooth approximation of the sign function, with Theorem 20, which establishes anticoncentration of the max of non-centered Gaussians. The particular g ∈ C 2 (R), g : R → [-1, 1] which we use is the following smooth approximator of the sign function:
Given parameters x ∈ R, β > 0, and δ > 0, define the function g x,β,δ (z) = g((z -x -e β )/δ). We record a simple claim that can be verified by direct calculation:
Claim 22. For any x ∈ R, β > 0 and δ > 0, the following hold:
We now proceed to prove (26). As before, for ease of presentation define the random variables
For arbitrary x ∈ R, β > 0, and δ > 0, we have
)
Setting β = (log k)/δ and δ = O(ε √ log k) 1/3 completes the proof of (26).
We conclude the proof of our PRG construction from the bound proved in Theorem 21; recall that this gives CDF-closeness at every point in R, specifically
Specializing this to CDF-closeness at the point 0, we get that
Now we recall that, from Section 4.2, all but a δ = ε fraction of outcomes V 1 , . . . , V k of V j = W j A T satisfy (8). Hence we have
and recalling that a draw Z from our generator Gen is Z = A T G (d) , we get that this is equivalent to
Setting ε = ε 3 / log 2 k completes the proof of correctness of our PRG construction.
In this section we prove Theorems 4 and 5, which we state with precise bounds as two parts of the following theorem.
Theorem 23 (Restatements of Theorem 4 and 5).
LTFs h 1 , . . . , h k over {-1, 1} n , an explicit function g : {-1, 1} k → {-1, 1}, and an error
time and outputs a value ṽ ∈ [0, 1] such that |ṽ -v| ≤ ε, where v is the fraction of points in {-1, 1} n that satisfy g(h 1 , . . . , h k ).
h 1 , . . . , h k over {-1, 1} n and an error parameter ε > 0, runs in poly(n) • 2 poly(log k,1/ε) time and outputs a value ṽ
We prove Part 1 first since it is simpler and relies on (extensions of) known tools such as regularity lemmas and invariance principles. In particular, Part 1 requires an invariance principle for arbitrary functions of LTFs. Such an invariance principle was proved in [14]; we provide an alternate proof of the invariance principle that we require in Appendix C, which we believe could be of independent interest. For Part 2, the main ingredients are an invariance principle of [16] for intersections of LTFs and a "multi-regularity lemma" for k-tuples of LTFs due to [14] along with a subtle application of the PRG for intersections of LTFs due to [28].
Given an LTF h(x) = sign(w
Intuitively, τ -regularity (when τ is small) captures the property that no weight in w 1 , . . . , w n has magnitude which is large relative to "the overall scale of the weights." Regularity is a useful condition because if w is a τ -regular weight vector with two-norm 1, then by the Berry-Esseen theorem [1, 10] the CDF of the real random variable w • X (where X is uniform over {-1, 1} n ) is τ -close to the CDF of an N (0, 1) Gaussian. Thus the Berry-Esseen theorem implies that regular LTFs will "behave similarly" whether they are given uniform inputs X ← {-1, 1} n or Gaussian inputs G ← N (0, 1) n ; in this sense, it can be viewed as an invariance principle for a single LTF. The first principal ingredient that we use is an invariance principle for arbitrary functions of LTFs. As mentioned earlier, such a result was established in [14] via a "Lindeberg-method" type proof. In Appendix C we give an alternate proof (which is very different from the proofs of [14,16]) of the version that we require, which is stated below:
Theorem 24 (Invariance principle for arbitrary functions of k LTFs). Let h 1 , h 2 , . . . , h k be τ -regular LTFs and let F (x) = g(h 1 (x), • • • , h k (x)) where g : {-1, 1} k → {-1, 1} may be any function. Then
Combining Theorem 2 (our PRG for arbitrary functions of LTFs over Gaussian space) and Theorem 24, an algorithm that simply enumerates over all the seeds of our PRG yields the following deterministic approximate counting algorithm for intersections of sufficiently regular LTFs:
There is a deterministic algorithm with the following performance guarantee: Given ε > 0, a collection h 1 , . . . , h k of LTFs over {-1, 1} n each of which is τ -regular where τ = O(
), and a function g : {-1, 1} k → {-1, 1}, the algorithm runs in time
) and outputs a value ṽ ∈ [0, 1] such that |ṽ -v| ≤ ε, where v is the fraction of points in {-1, 1} n that satisfy g(h 1 , . . . , h k ).
We next extend Corollary 25 to obtain a deterministic approximate counting algorithm for arbitrary functions of k general LTFs using a slight extension of the "multi-regularity lemma" established in [14] (see Theorem 5.4 of the ArXiV version, available at [15]) for k-tuples of general LTFs.
While not precisely stated in these terms, we recall that this multi-regularity lemma, roughly speaking, asserts the following: Given a k-tuple of LTFs h 1 , . . . , h k , there is a relatively shallow non-adaptive decision tree on the variables such that for all i ∈ [k], one of the two following two possibilities hold: 1. For every leaf ρ of the decision tree (corresponding to a restriction), the restricted LTF h i ρ is regular. 2. With high probability, the restricted LTF h i ρ is close to a constant. Similar to Lemma 18 of [7], the multi-regularity lemma of [14] can be implemented as a deterministic algorithm. In fact, because the decision tree is non-adaptive, the set of variables appearing in the internal nodes can be computed in time polynomial in depth of the decision tree (as opposed to exponential in the depth which is the size of the tree). This is because at each node, in order to choose which variable from x 1 , . . . , x n should be placed at that node it suffices to compute the influence of each variable in each of the k restricted linear forms, and this is a straightforward deterministic computation. We remark that the ability to compute the tree in polynomial time (in terms of its depth) is not crucial for this subsection. However, it is vital for the application in the next subsection -deterministic counting for intersections of general LTFs. Viewed as an algorithmic procedure from this perspective, Theorem 5.4 of [15] yields the following in our setting: Lemma 26 (Algorithmic regularity lemma for LTFs, general k, based on Theorem 5.4 of [15]).
There is an algorithm ConstructTree with the following properties: Let h 1 , . . . , h k be LTFs over {-1, 1} n . Algorithm ConstructTree (which is deterministic) receives h 1 , . . . , h k and C C C 2 0 1 9
PRGs from Gaussian Processes 0 < τ, γ < 1/4 as input, runs in time poly(n, D k (τ, γ)) and outputs a set of variables S ⊆ [n] and a k-tuple of labels (label 1 , . . . , label k ) ∈ {R, J} k such that the following holds:
2. For each leaf ρ and i ∈ [k], if label i = R, then the LTF h i ρ is τ -regular.
For each i ∈ [k], if label i = J, then the LTF h i obtained by zeroing the coordinates outside
In particular, observe that for any leaf ρ, h i ρ is fixed at either +1 or -1.
Remark 27. The theorem above can be obtained by essentially observing the proof of Theorem 5.4 in [15]. In particular, the S in the above theorem corresponds to the H 0 in their theorem. Similarly, the coordinates i ∈ [k] which are labeled 'R' (resp. labeled 'J') in our theorem correspond exactly to the coordinates i ∈ [d] which fall in the first case (resp. second case) of Theorem 5.4 in [15]. To get the guarantee for the third case, we define h i as follows. Let h i (x) = sign( j w i,j x j -θ j ). We then define h i (x) = sign( j∈S w i,j x j -θ j ), i.e., simply erase the coordinates outside of S. The upper bound on the quantity Pr x∈{-1,1} n [h i (x) = h i (x)] can essentially be derived from the event whose probability is upper bound in the centered equation in item (2) of Theorem 5.4 of [15].
We now extend the algorithm in Corollary 29 to handle arbitrary functions of k general LTFs using the algorithmic regularity lemma for multiple LTFs given in Lemma 26. The parameter"δ" in Lemma 26 is set to ε and the parameter "γ" is set to ε/k, and the parameter "τ " is set to O(
) so that Corollary 25 can be applied. Constructing the decision tree in the first step of the algorithm for general LTFs takes time poly(n, D k (τ, ε, δ)) = poly(n, k, 1/ε). In the second step of the algorithm for general LTFs, for each leaf ρ in the decision tree, If any of the k labels are "fail" the contribution from that leaf is 0;
If all k labels are bits b 1 , . . . , b k ∈ {-1, 1}, then the contribution from that leaf is 2
If k -t of the labels (for notational convenience, say these are the ones corresponding to h t+1 , . . . , h k ) are bits b t+1 , . . . , b k and the remaining t labels (say the ones corresponding to h 1 ρ, . . . , h t ρ) are "regular," we run the approximate counting algorithm for the regular case from Corollary 25 to compute an ±ε-accurate estimate (call it v ρ ) of the fraction of satisfying assignments of g((
The overall running time for the algorithm is at most poly(n)• (number of leaves) • (running time of Corollary 25), which is poly(n) • 2 Õ(k 3/2 /ε)+ Õ(k 15 /ε 12 ) . To establish correctness, we observe that the final value ṽ may be viewed as a sum of contributions across all the leaves. Property 3 of Lemma 26 and the setting of δ = ε in Step 1 ensures that leaves that have any "fail" label contribute a total of O(ε) to the error |v -ṽ|. The setting of the γ parameter to be ε/k ensures that leaves containing any +1 label, or having all -1's as their labels, collectively contribute a total of at most O(ε) to |v -ṽ|. Finally, Theorem 2 ensures that leaves as in the last bullet above contribute a total of O(ε) to |v -ṽ|. This concludes the proof of Theorem 23.
We begin by recalling the main structural result of [16], which extends the Berry-Esseen theorem to intersections of LTFs (also known as polytopes). (Recall that we view -1 as "true" and +1 as "false.") Theorem 28 (Theorem 3.1 of [16]: invariance principle for polytopes). Let h 1 , h 2 , . . . , h k be τ -regular LTFs and let
where C is an absolute constant.
Combining Theorem 3 (our PRG for intersections of LTFs over Gaussian space) and Theorem 28, an algorithm that simply enumerates over all the seeds of our PRG yields the following deterministic approximate counting algorithm for intersections of sufficiently regular LTFs: Corollary 29 (Deterministic approximate counting for intersections of regular LTFs). There is a deterministic algorithm with the following performance guarantee: Given ε > 0 and a collection h 1 , . . . , h k of LTFs over {-1, 1} n , each of which is τ -regular where τ = O(
The above algorithm works only for intersections of sufficiently regular LTFs. We will now extend Corollary 29 to obtain a deterministic approximate counting algorithm for intersections of k general LTFs using two tools. The first is the multi-regularity lemma (Lemma 26) from the previous subsection. The second ingredient we require is the recent construction of a PRG for intersection of LTFs by O'Donnell, Servedio and Tan [28] where they construct a PRG for the uniform distribution on {-1, 1} n which fools intersections of k LTFs with seed length (log n) • poly(log k, 1/ε). More precisely, we have the following theorem from [28].
Observe that while G OST simultaneously achieves polylogarithmic dependence on both n and k, to get a deterministic approximate counting algorithm with the kind of guarantee we want, we would need a seed length of the form log n + poly(log k, 1/ε). While we will crucially use G OST , we will essentially bootstrap it with the algorithms from Corollary 29 and Lemma 26 as follows.
Given as input h 1 , . . . , h k and a desired accuracy parameter ε, the algorithm proceeds as follows: 1. Run the algorithm ConstructTree on the LTFs h 1 , . . . , h k with its "γ" parameter as ε/4k and "τ " parameter as O(
The analysis of the running time of the above routine is straightforward: Observe that for our choice of τ and γ, the value D k (τ, γ) (from Lemma 26) is Õ(k • ε -5 ). The running time of the first step, i.e., ConstructTree is bounded by poly(n, D k (τ, γ)). Now, observing that |S| ≤ D k (τ, γ), from Theorem 30, we get that s OST = poly(log k, ε -foot_4 ) and thus |O OST | = 2 poly(log k,ε -1 ) . For each ρ ∈ O OST , the running time of the algorithm from Lemma 26 is bounded by poly(n)•2 Õ(log 6 k/ε 6 ) . Thus, the total running time is
We now move to the proof of correctness of the algorithm. Observe that if label i = J for any i ∈ [k], then by guarantee of Lemma 26,
Now, consider any assignment z ∈ {-1, 1}
[n]\S of the variables in [n] \ S. Then, using the guarantee of G OST , we get
Averaging over all possible values of z ∈ {-1, 1}
Now, observe that for any ρ ∈ O OST , h i (z, ρ) = h i (ρ) (since h i does not depend on the variables outside S). Further, for each i ∈ A R , the LTF h i ρ is τ -regular. Consequently, for each choice of ρ, Step 4 of our routine outputs v ρ such that
Averaging it over all choices of ρ, we get that output in the final step E ρ∈O OST [v ρ ] satisfies
Combining this with (29) finishes the proof.
In the analysis of our PRGs for arbitrary functions of k LTFs and for intersections of k LTFs, we assumed that we can sample from d-dimensional Gaussians, but to do this with perfect fidelity clearly requires infinitely many random bits. In this section we show that O(d log(kd/ε)) truly random bits suffice to produce d-dimensional "approximate Gaussian" distributions that suffice for our applications.
Definition 33. We say that a random variable G on R is a δ-approximate Gaussian random variable if there is a standard (correlated) Gaussian Ĝ such that Pr[|G -Ĝ| > δ] < δ.
We recall a lemma proved by Kane [22] which generates such approximate Gaussians in a randomness efficient way. It is based on the Box-Muller transform.
). There is an explicit construction of a δ-approximate Gaussian random variable using O(log(1/δ)) bits of randomness.
Let G d be a N (0, 1) d Gaussian. Let Ĝ(d) denote a coordinate-wise independent distribution in which the i-th coordinate Ĝ(d) i is a δ-approximate Gaussian random variable with respect to G (d) i as given by Lemma 34. We set (with foresight) the parameter δ = ε/(k √ d). By Lemma 34, a draw of Ĝ(d) can be generated using O(d log(kd/ε)) bits of randomness. Below we prove that Ĝ(d) can be used instead of G d in our PRGs, at the cost of an additional additive ε error for our PRG.
Let X = V G (d) -θ and X = V Ĝ(d) -θ. We prove that the "union-of-orthants" distance d UO (X, X) between X and X (see (18)) is at most ε. This directly implies that the approximation works since, as observed in Section 5.3, for any function g : {-1, 1} k → {-1, 1}, we have Pr[g(sign(X 1 ), . . . , sign(X k )) = 1] -Pr[g(sign( X1 ), . . . , sign( Xk )) = 1] ≤ d UO (X, X).
In order to prove that d UO (X, X) ≤ ε, we recall some definitions from Section 5.3. Recall that Our proof of Theorem 24 closely parallels the arguments underlying our PRG for arbitrary functions of k LTFs that were given in Section 5. However, for technical reasons we will now be using the (non-quadratic) Wasserstein distance. We recall the definition of this distance measure between distributions that we will use. (As was the case earlier for quadratic Wasserstein distance, there is an equivalent formulation in terms of Lipschitz test functions, but we will not need this alternative formulation.)
Definition 35. For any two distributions X and Y over R k , the Wasserstein distance between X and Y is defined to be
where the infimum is taken over all couplings ( X, Y) of X and Y.
As in the analysis of our PRG for arbitrary functions of k LTFs, we need an upper bound on the Wasserstein distance between the two random variables of interest as a starting point. In Section 5 the two relevant random variables were both multi-dimensional Gaussians and the desired (quadratic) Wasserstein closeness was given by Proposition 8. In the context of Theorem 24, the two relevant random variables are (i) a sum of independent vector-valued random variables and (ii) the Gaussian with matching mean and covariance, so it is natural to turn to the literature on central limit theorems for sums of vector-valued random variables for the desired upper bound on Wasserstein distance.
A range of central limit theorems for sums of independent vector-valued random variables have been established in the literature, but we are not aware of one which can be used "out of the box" for our purposes. Valiant and Valiant [32] gave a central limit theorem which upper bounds the Wasserstein distance between a sum of n vector-valued random variables and the corresponding Gaussian, but their quantitative bound has a log n factor which would spoil our desired final result. Zhai [33] gave a variant of the [32] CLT, but only for the setting of
We note that a weak form of Theorem
2, with a seed length of O log n + poly(2 k , 1/ε) , follows immediately from Theorem 3 just by setting its error parameter to be ε/2 k and observing that any function of k LTFs is a union of at most 2 k many disjoint intersections of k LTFs. However, this is exponentially worse than we achieve in Theorem 2 above.
By the Kantorovich-Rubinstein duality theorem, there is an equivalent formulation W2(X, Y) in terms of Lipschitz test functions, but we will not need this alternative formulation.
Chatterjee's original argument in [4] bounds the difference in the expectations of max j∈[k] (W j •G (n) -θ j ) and max j∈[k] (V j • G (n) -θ j ), corresponding to the identity function g(x) = x.
Andrew C. Berry. The accuracy of the Gaussian approximation to the sum of independent variates. Transactions of the American Mathematical Society, 49(1):122-136, 1941.
R. Bhatia. Matrix analysis, volume 169. Springer, 2013.
Thomas Bonis. Rates in the Central Limit Theorem and diffusion approximation via Stein's Method. arXiv preprint, 2015. arXiv:1506.06966.
Sourav Chatterjee. An error bound in the Sudakov-Fernique inequality. arXiv preprint, 2005. arXiv:math/0510424.