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.


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.