New Pseudorandom Generators and Correlation Bounds Using Extractors

Our knowledge of hardness and PRG results for ${\mathrm{𝖠𝖢}}^0$ is far more developed than that of ${\mathrm{𝖳𝖢}}^0$. Our state of the art PRGs for ${\mathrm{𝖠𝖢}}^0$ is Lyu’s construction [22], which $\epsilon$-fools polysize ${\mathrm{𝖠𝖢}}^0$ circuits with seed length $\tilde{O}({\log }^{d-1}(n)\log (n/\epsilon ))$, whereas the current best PRG of Hatami, Hoza, Tal, and Tell which $(2^{-n^{\delta }})$-fools size- $O(n^{1+\delta })$ ${\mathrm{𝖳𝖢}}^0$ circuits have seed length $O(n^{1-\delta })$ [15]. Due to this stark contrast in parameters, it is natural to gradually work upward from ${\mathrm{𝖠𝖢}}^0$ by allotting a budget of $\mathrm{𝖲𝖸𝖬}$ (calculates an arbitrary symmetric function) or $\mathrm{𝖳𝖧𝖱}$ (calculates an arbitrary linear threshold function) gates in the circuit. This approach has been explored for more than a decade [28, 20, 26], building upon the study of PRGs for $\{\mathrm{𝖲𝖸𝖬},\mathrm{𝖳𝖧𝖱}\}\circ {\mathrm{𝖠𝖢}}^0$ circuits pioneered by Luby, Velicković, and Wigderson [21]. This context explains why this circuit class a compelling generalization of sparse polynomials (which can be written as a small-size parity of ands). All the mentioned works use the following function introduced by Razborov and Wigderson in 1993 [25] (all arithmetic is over ${𝔽}_2$).

Most recently, Servedio and Tan [26] use ${\mathrm{𝖱𝖶}}_{m,k,r}$ to uncorrelate against constant-depth size-$n^{O(\log n)}$ ${\mathrm{𝖠𝖢}}^0$ circuits whose top gate is $\{\mathrm{𝖲𝖸𝖬},\mathrm{𝖳𝖧𝖱}\}$ (denoted as $\{\mathrm{𝖲𝖸𝖬},\mathrm{𝖳𝖧𝖱}\}\circ {\mathrm{𝖠𝖢}}^0$). Their explicit bound is

Via techniques used in [20], this can be translated to correlation bounds against ${\mathrm{𝖠𝖢}}^0$ circuits with up to $n^{.499}$ $\mathrm{𝖲𝖸𝖬}$ gates or $n^{.249}$ $\mathrm{𝖳𝖧𝖱}$ gates. As can be surmised by the repeated occurrences of $n^{.499}$, the strength of the correlation bound dictates how many $\{\mathrm{𝖲𝖸𝖬},\mathrm{𝖳𝖧𝖱}\}$ gates we can afford in our budget.

We show that $\mathrm{𝖱𝖶}$ is just one of many functions from a general class of hard functions with small correlation against $\{\mathrm{𝖲𝖸𝖬},\mathrm{𝖳𝖧𝖱}\}\circ {\mathrm{𝖠𝖢}}^0$ circuits. For functions $f:{({\{0,1\}}^r)}^k\to \{0,1\}$ and $g:{\{0,1\}}^m\to {\{0,1\}}^r$, denote $f\circ g^k(x_1\mathrm{\dots },x_k):=f(g(x_1),\mathrm{\dots }g(x_k)).$

To our knowledge, this theorem gives the first context where generically precomposing with an extractor boosts correlation bounds whose proof does not rely on simplification under random restriction (indeed parity does not simplify under restriction and is contained in $\{\mathrm{𝖲𝖸𝖬},\mathrm{𝖳𝖧𝖱}\}\circ {\mathrm{𝖠𝖢}}^0\}$). Previously, extractors have only been used to boost correlation bounds for classes that heavily simplify under random restriction [18, 8].²²2There have been uses of extractors as a hard function against classes that do not simplify under restriction, like DNFs of Parities [9] and strongly read-once linear branching programs [12, 19, 7]. However they directly establish a correlation bound against the extractor rather than amplify a weaker hard function by precomposing with an extractor. Our theorem states that extractors can still boost correlation bounds, even if they were proven using communication complexity rather than random restrictions.

Furthermore, our theorem distills out the reason why $\mathrm{𝖱𝖶}$ was so effective as a hard function. Quantitatively, we can instantiate the template with a suitable extractor to obtain a new hard function with nearly-optimal correlation bounds.

Due to our strengthened correlation bounds, we can now get correlation bounds and PRGs against size-$n^{O(\log n)}$ ${\mathrm{𝖠𝖢}}^0$ circuits with up to $n^{.999}$ $\mathrm{𝖲𝖸𝖬}$ gates or $n^{.499}$ $\mathrm{𝖳𝖧𝖱}$ gates. Prior to this, no nontrivial correlation bound or PRG was known to handle such large size and number of $\{\mathrm{𝖲𝖸𝖬},\mathrm{𝖳𝖧𝖱}\}$ gates ([20] could handle the same number of $\{\mathrm{𝖲𝖸𝖬},\mathrm{𝖳𝖧𝖱}\}$ gates but only for $n^{O(\log \log n)}$-size circuits, and [26] could handle the same size circuits, but only $n^{.499}$ $\mathrm{𝖲𝖸𝖬}$ or $n^{.249}$ $\mathrm{𝖳𝖧𝖱}$ gates).

Even for $\{\mathrm{𝖲𝖸𝖬},\mathrm{𝖳𝖧𝖱}\}\circ {\mathrm{𝖠𝖢}}^0$ circuits which have only one $\{\mathrm{𝖲𝖸𝖬},\mathrm{𝖳𝖧𝖱}\}$ gate, our correlation bounds yields improved PRGs whose seed length is $2^{O(\sqrt{\log S})}+{(\log (1/\epsilon ))}^{2.01}$, which has a better dependence on $\epsilon$, than previous work (see Table 1). In fact, since the best correlation bound one can hope for is $2^{-\mathrm{\Omega }(n)}$, this dependence is almost optimal under the Nisan-Wigderson framework, and an alternative approach is needed to reach the optimal dependence of $\log (1/\epsilon )$. Since any $\log n$-degree ${𝔽}_2$ polynomial can be expressed as a $\mathrm{𝖲𝖸𝖬}\circ {\mathrm{𝖠𝖭𝖣}}_{\log n}$ circuit of size $n^{\log n}$, any improvement of the dependence of the seed length on $S$ would give nontrivial PRGs for $\log n$-degree polynomials, a breakthrough result.

Usually, one constructs PRGs for natural computational models, with the idea that we can drastically reduce the randomness we use if the randomized algorithm we are running can be simulated by such a model. Low degree polynomials is an extremely natural mathematical model with applications to circuit complexity, but some may not believe it is well grounded as a computational one and thus not worth finding a PRG for. However, the work of Bogdanov, Dvir, Verbin, and Yehudayoff [5] showed the beautiful connection that PRGs for degree $d$ polynomials are also PRGs against a particular model described as width-2 length-$\mathrm{𝗉𝗈𝗅𝗒}(n)$ branching programs which read $d$ bits at a time.

Such branching programs are a well motivated computation model which cover computation with only one bit of usable memory, low degree polynomials, and small width DNFs. The survey of unconditional PRGs by Hatami and Hoza refer to this model as a compelling computational model that places low degree polynomials in the computational landscape [14].

Unfortunately, there is a “$\log n$-degree barrier” for PRGs and correlation bounds against low degree polynomials. Current PRGs and correlation bounds are asymptotically tight for constant degree polynomials, but become trivial at degree $\log n$, as can be seen by the current best known PRG for degree-$d$ polynomials by Viola which has seed length $O(d\log n+d{2}^d\log (n/\epsilon ))$ [29]. Getting nontrivial PRGs (or even correlation bounds) against $\log n$-degree polynomials has been a tantalizing and longstanding open problem, and thus PRGs for $(d,\mathrm{𝗉𝗈𝗅𝗒}(n),n)$-2BPs also seemingly appeared to inherit this “$d=\log n$ barrier” due to the reduction result of [5].

In this work, we construct PRGs against $(d,\mathrm{𝗉𝗈𝗅𝗒}(n),n)$-2BPs with exponentially better seed length, thereby giving nontrivial PRGs even in the regime $d=n^{1-o(1)}$. Define a $d$-junta to be a function $\varphi :{\{0,1\}}^n\to \{0,1\}$ which is solely dependent on $d$ input bits (i.e. can be written as ${\varphi }^{\prime }{(x_i)}_{i\in S}$ for some subset $S\subset [n]$ of size $d$). To get our shortened seed length, we evade the $\log n$-degree barrier by instead showing the equivalence between PRGs for $(d,\mathrm{𝗉𝗈𝗅𝗒}(n),n)$-2BPs and PRGs for the XOR of $\mathrm{𝗉𝗈𝗅𝗒}(n)$ many $d$-juntas (denoted as ${\mathrm{𝖩𝖴𝖭𝖳𝖠}}_{n,d}^{\oplus \mathrm{𝗉𝗈𝗅𝗒}(n)}$). This class is already interesting in its own right, as it can be seen as a generalization of sparse ${𝔽}_2$-polynomials and combinatorial checkerboards (defined by Watson [32] and also studied by Gopalan, Meka, Reingold and Zuckerman [11]), as well as a specific class bounded collusion protocols studied by Chattopadhyay et al. [6]. However, we are not aware of any literature studying ${\mathrm{𝖩𝖴𝖭𝖳𝖠}}_{n,d}^{\oplus m}$ specifically.

Our main technical contribution is strong correlation bounds for ${\mathrm{𝖩𝖴𝖭𝖳𝖠}}_{n,d}^{\oplus \mathrm{𝗉𝗈𝗅𝗒}(n)}$. In particular, we show the following.

By combining this with the “hardness-to-randomness” framework of Nisan and Wigderson [24], we construct a PRG of seed length $2^{O(\sqrt{\log n})}{d}^2{\log }^2(1/\epsilon )$. This is only a quadratic factor away from optimal dependence on $d$ and $\epsilon$. Improving the dependence on $n$ would be a breakthrough, since if we set $n^{\prime }=2^{\sqrt{\log n}}$, a $(d,n,\mathrm{𝗉𝗈𝗅𝗒}(n))$-2BP can simulate any $\log n^{\prime }$-degree polynomial over $x_1,\mathrm{\dots }{x}_{n^{\prime }}$, and so having seed length $o(n^{\prime })$ would effectively be breaking the $\log n$-degree barrier for ${𝔽}_2$-polynomial PRGs.

Interestingly enough, by combining an “simplification under restriction” approach pioneered by Ajtai and Wigderson [1] with a PRG for sparse ${𝔽}_2$-polynomials by Servedio and Tan [27], we are able to construct a PRG against ${\mathrm{𝖩𝖴𝖭𝖳𝖠}}_{n,d}^{\oplus \mathrm{𝗉𝗈𝗅𝗒}(n)}$, and thus $(d,\mathrm{𝗉𝗈𝗅𝗒}(n),n)$-2BPs, with seed length $d{2}^{O(\sqrt{\log (n/\epsilon )})}$. This gives us an optimal dependence on $d$, but an exponentially worse dependence on $\epsilon$. This suggests perhaps with a combination of these two approaches, one might be able to achieve seed length $2^{O(\sqrt{\log n})}d\log (1/\epsilon )$.

As explained earlier, a central open question in complexity theory is to establish better-than-$O(1/\sqrt{n})$ nontrivial correlation bounds against $\mathrm{\Omega }(\log n)$-degree polynomials. In order to make progress on this question, it is natural to consider structured low-degree ${𝔽}_2$-polynomials. This is what the work of Bhrushundi et al. does [3].

Define a polynomial $p:{\{0,1\}}^n\to \{0,1\}$ to be set-multilinear over a partition $X=(X_1,\mathrm{\dots },X_d)$ of the input bits if every monomial contains at most one variable from each $X_i$ (this is slightly more general than the usual definition of exactly one). The work of Bhrushundi et al. [3] prove that a random degree $d$ set-multilinear tensor has exponentially small correlation against generic degree $d/2$ ${𝔽}_2$-polynomials for $d=\mathrm{\Omega }(n)$. Towards making this correlation bound explicit, they defined $\mathrm{𝖥𝖥𝖬}(X_1,\mathrm{\dots },X_d)=\mathrm{𝗅𝗌𝖻}(X_1\cdot X_2\mathrm{\cdots }{X}_d)$, where multiplication is done by treating the $X_i$ as field elements, and $\mathrm{𝗅𝗌𝖻}$ outputs the least significant bit of the string. Bhushrundi et al. were able to give exponentially small correlation bounds against polynomials up to degree $o(n/\log n)$ which are set-multilinear over the fixed partition $(X_1,\mathrm{\dots },X_d)$. However, this leaves more to be wanted. The partition with respect to which the polynomial is set-multilinear over needing to be fixed and dependent on ${\mathrm{𝖥𝖥𝖬}}_d$ feels like an extremely strong and asymmetric condition. Can we uncorrelate against degree polynomials set-multilinear over any equipartition of $X$ into $d$ parts? Can the parts be unequal? Can we have more than $d$ of them?

We show the affirmative to all the above questions. If we take $\delta >0$ to be an arbitrarily small constant, we can obtain exponentially small correlation against degree polynomial for which there exists some partition of $X$ into up to $n^{1-\delta }$ (not necessarily equal) parts such that $p$ is set-multilinear over it. Notice improving $n^{1-\delta }$ parts to $n$ would be a breakthrough, since all polynomials are set-multilinear over the $n$-partition of $X=(x_1,\mathrm{\dots },x_n)$.

To do so, we fortify the hard function $\mathrm{𝖥𝖥𝖬}$ with an extractor. Let $\mathrm{𝖤𝗑𝗍}(X,W)$ be a strong linear seeded extractor (for each fixing of $W$, $\mathrm{𝖤𝗑𝗍}(\cdot ,W)$ is linear). For some parameter $d$, define the function

where multiplication is done over a finite field, and $\mathrm{𝗅𝗌𝖻}$ outputs the least significant bit of the string. First note that ${\mathrm{𝖤𝗑𝗍𝖥𝖥𝖬}}_d(X_1,\mathrm{\dots },X_d,W)$, for a fixed $W$, is set-multilinear over $X_1,\mathrm{\dots },X_d$. Hence our intuition that set-multilinear polynomials might correlate the most with the hard function is preserved in $\mathrm{𝖤𝗑𝗍𝖥𝖥𝖬}$ as well. Using $\mathrm{𝖤𝗑𝗍𝖥𝖥𝖬}$, we are able to obtain correlation bounds against the more intuitive notion of set-multilinear polynomials, where the structure of the partition does not matter. This gives more leeway since now if we want to implement this approach towards correlation bounds against low-degree polynomials, there is a larger class of set-multilinear polynomials that we can reduce generic polynomials to.

We focus on showing stronger correlation bounds against $\{\mathrm{𝖲𝖸𝖬},\mathrm{𝖳𝖧𝖱}\}\circ {\mathrm{𝖠𝖢}}^0$, since the subsequent arguments turning this into PRGs against ${\mathrm{𝖠𝖢}}^0$ with a few $\{\mathrm{𝖲𝖸𝖬},\mathrm{𝖳𝖧𝖱}\}$ gates are standard. The blueprint behind this argument follows the “simplification under restrictions” approach of previous works, but most similarly of Tan and Servedio [26]. A random restriction is a random partial assignment where for each variable, it is left unfixed (or “alive”) with probability $p$, and is otherwise set to a uniform bit. [26] shows that under a random restriction, the hard function ${\mathrm{𝖱𝖶}}_{m,k,r}$ maintains integrity and uncorrelates against multiparty protocols, while the $\{\mathrm{𝖲𝖸𝖬},\mathrm{𝖳𝖧𝖱}\}\circ {\mathrm{𝖠𝖢}}^0$ simplifies to a short multiparty protocol. However, the roadblock met in [26] preventing a correlation bound of $2^{-\mathrm{\Omega }(n)}$ and only giving one of size $2^{-\mathrm{\Omega }(n^{.499})}$ is due to parameters in ${\mathrm{𝖱𝖶}}_{m,k,r}$ being in contention with each other. To elucidate, if $n$ is the input size, then we must have $mkr=n$. Via the analysis done in [26], the correlation bound ends up being in the form of $2^{-\mathrm{\Omega }(m)}+2^{-\tilde{\mathrm{\Omega }}(r)}$, which forces any established correlation bound to be at best $2^{-\mathrm{\Omega }(\sqrt{n})}$.

To understand why both conflicting terms show up, we give a quick overview of the argument of [26]. First, ${\mathrm{𝖱𝖶}}_{m,k,r}$ (as defined in Equation 1) can be thought of as a fortified version of the generalized inner product, ${\mathrm{𝖦𝖨𝖯}}_{m,k}(x_1,\mathrm{\dots },x_k):={\sum }_{i=1}^m{\prod }_{j=1}^k{x}_{ij}$, where each variable is now replaced by the parity of $r$ new variables. This is effective against random restrictions, since as long as one of the $r$ copies $x_{ij1},\mathrm{\dots },x_{ijr}$ survive the restriction, the corresponding term $x_{ij}$ in $\mathrm{𝖦𝖨𝖯}$ will survive. They argue that after a random restriction $\rho$ is applied, the $\{\mathrm{𝖲𝖸𝖬},\mathrm{𝖳𝖧𝖱}\}\circ {\mathrm{𝖠𝖢}}^0$ circuit simplifies to a short multiparty protocol, while ${{\mathrm{𝖱𝖶}}_{m,k,r}|}_{\rho }$ is still capable of computing ${\mathrm{𝖦𝖨𝖯}}_{m/2,k}$ with high probability. Conditioning upon this, previous results of Babai, Nisan, and Szegedy [2] show that ${\mathrm{𝖦𝖨𝖯}}_{m/2,k}$ has $2^{-\mathrm{\Omega }(m/2^k)}$ correlation against these multiparty protocols, explaining the emergence of the $2^{-\mathrm{\Omega }(m)}$ term in the correlation.  Conditioning on ${{\mathrm{𝖱𝖶}}_{m,k,r}|}_{\rho }$ being able to compute ${\mathrm{𝖦𝖨𝖯}}_{m/2,k}$ introduces an additive error to the correlation corresponding to the probability ${{\mathrm{𝖱𝖶}}_{m,k,r}|}_{\rho }$ fails to simplify. [26] bounds this by the chance all $r$ copies of some variable $x_{ij}$ becomes fixed by a restriction, which will be ${(1-p)}^r\approx \exp (-pr)$, explaining the occurrence of the $2^{-\mathrm{\Omega }(r)}$ term in the correlation.

In summary, the argument of [26] requires $r$ needs to be large to strongly fortify the hard function against random restrictions, while $m$ needs to be large to have a stronger correlation bound against multiparty protocols. However, with the constraint $mr\le n$, we are forced to compromise and reach the setting $m=r\approx \sqrt{n}$.

We now propose an abstraction of the hard function, which naturally yields a stronger correlation bound. If we define ${\oplus }_{m,r}:{({\{0,1\}}^r)}^m\to {\{0,1\}}^m$ to be

we observe ${\mathrm{𝖱𝖶}}_{m,k,r}={\mathrm{𝖦𝖨𝖯}}_{m,k}\circ {\oplus }_{m,r}^k(x_1,\mathrm{\dots },x_k):={\mathrm{𝖦𝖨𝖯}}_{m,k}({\oplus }_{m,r}(x_1),\mathrm{\dots },{\oplus }_{m,r}(x_k))$. The key insight is that our argument can be generalized to not just $\mathrm{𝖱𝖶}$, but any function

where $f$ is average-case hard for multiparty protocols, and $\mathrm{𝖤𝗑𝗍}$ is an oblivious bit-fixing source extractor (OBF extractor). Informally, an oblivious bit-fixing source extractor for min-entropy $k$ is a function $\mathrm{𝖤𝗑𝗍}$ such that if $𝐗$ is uniform over ${\{0,1\}}^n$ and $\rho$ is a restriction which leaves $\ge k$ bits alive, the output $\mathrm{𝖤𝗑𝗍}({𝐗|}_{\rho })$ is close to uniform. Recall our approach first applies a random restriction to simplify our circuit to a small multiparty protocol, which we then deal with using $\mathrm{𝖦𝖨𝖯}$. If the random restriction leaves sufficiently many variables alive with high probability, then $f\circ {\mathrm{𝖤𝗑𝗍}}^k$ should still behave like $f$ due to $\mathrm{𝖤𝗑𝗍}$ being an OBF extractor. Since the circuit is now a multiparty protocol, the average-case hardness of $f$ gives us a correlation bound.

Notice in the $\mathrm{𝖱𝖶}$ construction and the setting of parameters $m=r\approx \sqrt{n}$, ${\oplus }_{m,r}$ is an OBF extractor which maps $n$ bits to $\sqrt{n}$ bits. But this means the input to the outer $\mathrm{𝖦𝖨𝖯}$ function will only have $\approx \sqrt{n}$ bits, and so the best correlation bound we can hope to achieve is $\exp (-\mathrm{\Omega }(\sqrt{n}))$. The restrictions used in the proof leave $n^{.99}$ variables alive with high probability, so intuitively we could hope that all these $n^{.99}$ “bits of randomness” could be preserved for $\mathrm{𝖦𝖨𝖯}$ (or in general any $f$) rather than only $\sqrt{n}$, potetially resulting in a $\exp (-\mathrm{\Omega }(n^{.99}))$ correlation bound alive. We do just this by using a much better OBF extractor of Kamp and Zuckerman [17]. By making this intuition more formal using techniques developed by Viola and Wigderson [31], we obtain $2^{-\mathrm{\Omega }(n^{1-O(1)})}$ correlation bound. The idea of replacing parities with better suited extractors has also appeared in previous work [18, 8].

Our PRG construction blueprint can be briefly described as follows. We first establish correlation bounds against ${\mathrm{𝖩𝖴𝖭𝖳𝖠}}_{n,d}^{\oplus t}$. We then put this through the Nisan-Wigderson “hardness vs. randomness” framework to create a PRG against ${\mathrm{𝖩𝖴𝖭𝖳𝖠}}_{n,d}^{\oplus t}$. We then show that PRGs which fool ${\mathrm{𝖩𝖴𝖭𝖳𝖠}}_{n,d}^{\oplus t}$ actually fool $(d,t,n)$-2BPs, making the ${\mathrm{𝖩𝖴𝖭𝖳𝖠}}_{n,d}^{\oplus t}$ PRG our final construction. We first discuss why PRGs for ${\mathrm{𝖩𝖴𝖭𝖳𝖠}}_{n,d}^{\oplus t}$ imply PRGs for $(d,t,n)$-2BPs, and then discuss the techniques needed to show strong correlation bounds against ${\mathrm{𝖩𝖴𝖭𝖳𝖠}}_{n,d}^{\oplus t}$.

We will once again use $f\circ {\mathrm{𝖤𝗑𝗍}}^k$ as our hard function⁴⁴4we also precompose with parities in the formal argument to establish exponentially small correlation bounds against the class, and then apply the Nisan-Wigderson [24] framework to construct the PRG. The latter portion is straightforward, so we focus on establishing the correlation bounds.

Let $g\in {\mathrm{𝖩𝖴𝖭𝖳𝖠}}_{n,d}^{\oplus \mathrm{𝗉𝗈𝗅𝗒}(n)}$. We first show that there exist a subset of variables, $S$, such that upon arbitrarily fixing bits outside of this set, $g$ can be expressed as a sparse ${𝔽}_2$ polynomial, whereas each input block of $f\circ {\mathrm{𝖤𝗑𝗍}}^k$ heavily intersect $S$. Hence if we fix $X_{\overline{S}}$ and take the correlation over $S$, each input block still maintains high min-entropy while $g$ becomes a sparse polynomial, which is a small $\mathrm{𝖲𝖸𝖬}\circ {\mathrm{𝖠𝖢}}^0$ circuit. Since the hard function is also the same, we can then apply techniques in the previous section to conclude.

Recall that [3] has shown ${\mathrm{𝖥𝖥𝖬}}_d$ uncorrelates against any lower degree polynomial which is set-multilinear over $(X_1,\mathrm{\dots },X_d)$. The key ingredient behind proving strong correlation bounds against set-multilinear polynomials over arbitrary parititons is to first fortify each input block with extractors, and instead consider ${\mathrm{𝖤𝗑𝗍𝖥𝖥𝖬}}_d$. This allows us to establish the following structural lemma, which intuitively states that even if you do not start out with a polynomial that is set-multilinear over $(X_1,\mathrm{\dots },X_d)$, if not too many bits in each input block can be restricted to 1s such that the resulting function is set-multilinear over $(X_1,\mathrm{\dots },X_d)$ induced by the live variables in each block, exponential correlation bounds can still be obtained.

To explain the proof at a high level, if the sets $S_i$ we leave alive aren’t too small, then our strong extractor (conditioned on a good seed) will keep each block $\mathrm{𝖤𝗑𝗍}(X_i,W)$ approximately uniform, and since the restricted function ${g|}_{\rho }$ is now set-multilinear over $(X_1,\mathrm{\dots },X_d)$ we may use a similar approach as [3] to prove the theorem.

It turns out that via a combinatorial argument, one can show that polynomials which are set-multilinear over a large number of blocks can be turned into polynomials set-multilinear over $(X_1,\mathrm{\dots },X_d)$ by fixing not too many bits per input block $X_i$. The correlation bounds then follow by the structural lemma.

We will canonically fix a partition of bit strings into $d$ contiguous blocks, each with $n/d$ bits. In particular, any $X\in {\{0,1\}}^n$ can be written as $X=(X_1,\mathrm{\dots },X_d)$ where each $X_i$ is the $n/d$-bit substring. If a string $Y\in \{0,1\}$ is defined, $Y_i$ will be assumed to mean the length $n/d$ substring of $Y$ contained in the $i$th input block, defined with respect to the canonical partition. Also, we will denote $X_{-i}:=(X_1,\mathrm{\dots },X_{i-1},X_{i+1},\mathrm{\dots },X_d)$ to be the input with the $i$th block removed.

For a string $X\in \{0,1\}$, we may sometimes identify the $n/d$ bit string $X_i$ as an $n$-bit string in the following way: the $i$th block is filled with $X$, and all other blocks are filled with 0s. Hence, if we interpret bit strings as elements of ${𝔽}_2^n$, and we have $X,Y\in {𝔽}_2^n$, the expression $X+Y_i$ is well defined.

For parameters $k,d\le n$ and two functions $f:{({\{0,1\}}^m)}^k\to \{0,1\}$ and $g:{\{0,1\}}^{n/k}\to {\{0,1\}}^d$, we will define

We will be working with finite fields of characteristic 2. For the finite field over $2^n$ elements, ${𝔽}_{2^n}$, we can naturally identify each element with an $n$-bit string.

Since ${𝔽}_{2^n}$ is an $n$-dimensional vector space, we see the valuations on $n$ basis vectors uniquely define the character. Consequently there are $2^n$ such characters. Notice we can conveniently characterize all characters either by ${\chi }_c(x)=⟨x,c⟩$, or by fixing some character $\chi$, and then defining ${\chi }_c(x):=\chi (c\cdot x)$. This can be seen by verifying these maps are characters, are distinct, and that there are $2^n$ of them (the latter is obvious since there are $2^n$ values of $c$).

We will denote $U_m$ to be the uniform distribution over the finite set ${\{0,1\}}^m$. We will also denote $S{\subset }_{p}T$ to be a random subset of $T$ where each $t\in T$ is added to $S$ independently with probability $p$.

A partial assignment or restriction is a string $\rho \in {\{0,1,\star \}}^n$. Intuitively, a $\star$ represents an index that is still “alive” and hasn’t been fixed to a value yet.

We also define a composition operation on partial assignments. For two restrictions ${\rho }^1,{\rho }^2$, define ${\rho }^1\circ {\rho }^2$ so that

Intuitively, one can see this as fixing bits determined by ${\rho }^1$ first, and then out of the remaining alive positions, fix them according to ${\rho }^2$.

A random restriction is simply a distribution over restrictions. A common random restriction we will use is $R_p$, the distribution where each index will be assigned $\star$ with probability $p$, and $0,1$ each with probability $\frac{1-p}{2}$.

The main reason for defining restrictions is to observe their action on functions. Given a restriction $\rho$ and function $f:{\{0,1\}}^n\to \{0,1\}$, we define ${f|}_{\rho }:{\{0,1\}}^n\to \{0,1\}$ to be the restricted function mapping ${f|}_{\rho }(x):=f(\rho \circ x)$.

Our work will involve working with pseudorandomness primitives, like pseudorandom generators (PRGs) and randomness extractors (or simply extractors).

We will need some tools and definitions from the literature of correlation bounds. We first give a formal definition of correlation.

Viola and Wigderson defined a convenient quantity $R_k$, which is very useful in bounding correlations against NOF protocols.

This norm is useful due to the following theorem.

We will also use the following theorem of Nisan and Wigderson, which allow us to translate correlation bounds into PRGs.This version is seen in the survey of Hatami and Hoza [14]