Average-case analogue of Small-bias Spaces

Question

Recall that an $\epsilon$-biased space is a set $S \subset \{0,1\}^n$ such that for every non-zero linear test $\alpha \in \{0,1\}^n \setminus \{0\}^n$, the expected bias $$| \mathbb{E}_{x \in S} [ (-1)^{<x,\alpha>} ] | \leq \epsilon$$ is small. Distributions over such subsets $\epsilon$-fool all linear tests, so if we can make $|S|$ as small as possible, we have a good deranomization primitive.

Is an average case analogue of such a construction studied anywhere, and is it useful? More precisely, suppose we take a subset $S \subset \{0,1\}^n$ such that $$\mathbb{E}_{\alpha}| \mathbb{E}_{x \in S} [ (-1)^{<x,\alpha>} ] | \leq \epsilon$$ This is, of course, weaker than $\epsilon$-fooling all linear tests. My question is: is there a natural approach to constructing such a set $S$ of small size?

A method used to construct $\epsilon$-bias sets is to interpret it as the vectors of the parity-check matrix of an $\epsilon$-balanced linear code, and so the aim becomes to design such a code with as high rate as possible. Would such an approach work for the average-case too? I am unclear on the correspondence though.

Answer 1

Below I show how to explicity construct an average-case $\varepsilon$-biased space on $n$ bits of size $O(1/\varepsilon)$.

In contrast, the best worst-case $\varepsilon$-biased spaces on $n$ bits have size $\tilde\Theta(n/\varepsilon^2)$. So you save a factor of about $n/\varepsilon$ by going from worst-case to average-case.

Unfortunately, as you will see, the construction is a bit silly. This explains why this primitive has not been studied.

Let $m=\lceil \log_2(1/\varepsilon) \rceil$. Let $S = \{0,1\}^m \times \{0\}^{n-m} \subset \{0,1\}^n$. That is, a random $x \in S$ consists of $m$ uniformly random bits, followed by $n-m$ zeros.

We have $|S| = 2^m = 2^{\lceil \log_2 (1/\varepsilon) \rceil} \ge 2^{\log_2(1/\varepsilon)} = \frac{1}{\varepsilon}$ and, similarly, $|S| < 2^{\log_2(1/\varepsilon)+1} = \frac{2}{\varepsilon}$.

Now let's analyse the average bias of $S$: $$\underset{\alpha \in \{0,1\}^n}{\mathbb{E}}\left[\left|\underset{x \in S}{\mathbb{E}}\left[(-1)^{\langle x , \alpha \rangle}\right]\right|\right] = \underset{\alpha_0 \in \{0,1\}^m}{\mathbb{E}}\left[\left|\underset{x_0 \in \{0,1\}^m}{\mathbb{E}}\left[(-1)^{\langle x_0 , \alpha_0 \rangle}\right]\right|\right] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\\~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\le \underset{\alpha_0 \in \{0,1\}^m}{\mathbb{P}} \left[ \alpha_0 = (0,0,\cdots,0) \right] \cdot 1 + \underset{\alpha_0 \in \{0,1\}^m}{\mathbb{P}} \left[ \alpha_0 \ne (0,0,\cdots,0) \right] \cdot 0\\= 2^{-m} + 0 \le \varepsilon~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$$ The first line uses the fact that only the first $m$ bits are relevant and the second line uses the fact that $x_0$ is uniform.

Furthermore, we can show that $|S| \ge 1/\varepsilon$ is necessary -- a nearly matching lower bound. See this answer for the proof idea.