<p>recall that
<span class="math-container">$$\langle s(x,y,z),\tau\rangle=\cdots=f_z\Big(\sum_{i,j}x^iy^j\tau_{i,j}\Big)$$</span></p>

<p>if we define <span class="math-container">$p_\tau(x,y)=\sum\limits_{i,j}x^iy^j\tau_{i,j}$</span>, we have</p>

<p><span class="math-container">$$\langle s(x,y,z),\tau\rangle=f_{p_\tau(x,y)}(z)$$</span></p>

<p>So, observe that whenever <span class="math-container">$p_\tau(x,y)\neq 0$</span> we <strong>win</strong> as <span class="math-container">$z$</span> is uniform and the expected value of <span class="math-container">$f_{p_\tau(x,y)}(z)$</span> is also <span class="math-container">$1/2$</span> which means that the contribution to the bias of these <span class="math-container">$x,y$</span> is zero.</p>

<p>Again from Schwartz-Zippel we have only <span class="math-container">$O(\sqrt{n}/2^\ell)$</span> many zeros of <span class="math-container">$p_\tau$</span> on them we lose the entire bias. So, the total bias is at most <span class="math-container">$O(\sqrt{n}/2^\ell)\stackrel{?}{\leq}\varepsilon$</span>. Choosing <span class="math-container">$\ell=\Omega(\log(\sqrt{n}/\varepsilon))$</span> finishes the construction.</p>

CC BY-SA 4.0
2019-01-17T19:15:44.627Z
2019-01-17T19:27:58.867Z
2019-01-17T19:27:58.867Z
user621824
<p>Let <span class="math-container">$\ell&gt; 1$</span> be an integer and consider the mapping <span class="math-container">$\text{Tr}:\mathbb{F}_{2^\ell}\to\mathbb{F}_{2^\ell}$</span> defined by
<span class="math-container">$$\text{Tr}(x)=x^{2^0}+x^{2^{1}}+\cdots+x^{2^{\ell-1}}$$</span>
It is then possible to show the following </p>

<ol>
<li><span class="math-container">$\text{Tr}$</span> maps <span class="math-container">$\mathbb{F}_{2^\ell}$</span> into <span class="math-container">$\mathbb{F}_2$</span>.</li>
<li>If <span class="math-container">$a\in\mathbb{F}_{2^\ell}$</span> is non-zero, then the mapping <span class="math-container">$f_a:\mathbb{F}_{2^\ell}\to\mathbb{F}_{2}$</span> defined by <span class="math-container">$f_a(x)=\text{Tr}(a\cdot x)$</span> is <span class="math-container">$\mathbb{F}_2$</span>-linear and <span class="math-container">$\mathbb{E}_{x\sim\mathbb{F}_{2^\ell}}[f(x)]=\frac{1}{2}$</span>.</li>
</ol>

<p>Now, we consider the set <span class="math-container">$S=\{s(x,y,z):x,y,z\in\mathbb{F}_{2^\ell}\}$</span> such that we index the entries of <span class="math-container">$s(x,y,z)$</span> by <span class="math-container">$0\leq i,j$</span> such that <span class="math-container">$i+j\leq c\sqrt{n}$</span> (<span class="math-container">$c$</span> is a constant so that there are exactly <span class="math-container">$n$</span> entries). For such <span class="math-container">$x,y,z$</span> and <span class="math-container">$i,j$</span> we set <span class="math-container">$s(x,y,z)_{i,j}=\text{Tr}(x^iy^jz)$</span>.</p>

<p>I want to show that for an appropriate choice of <span class="math-container">$\ell$</span>, the set <span class="math-container">$S$</span> described above is an <span class="math-container">$\varepsilon$</span>-biased set of size <span class="math-container">$O(n\sqrt{n}/\varepsilon^3)$</span>.</p>

<p>Fix <span class="math-container">$\vec{0}\neq \tau\in\{0,1\}^n$</span>, <strong>what we need to show</strong> is that (under good choice of <span class="math-container">$\ell$</span>)
<span class="math-container">$$\bigg|\mathbb{E}_{s\in S}\Big[(-1)^{\langle s,\tau\rangle}\Big]\bigg|\leq \varepsilon$$</span> </p>

<p>Let <span class="math-container">$x,y,z\in\mathbb{F}_{2^\ell}$</span> and consider <span class="math-container">$\langle s(x,y,z),\tau\rangle$</span>, I managed to show that (from <span class="math-container">$\mathbb{F}_2$</span>-linearity above while indexing <span class="math-container">$\tau$</span> as we index <span class="math-container">$s(x,y,z)$</span>)
<span class="math-container">$$\langle s(x,y,z),\tau\rangle=\cdots=f_z\Big(\sum_{i,j}x^iy^j\tau_{i,j}\Big)$$</span>
Finally, I thought of defining the bi-variate polynomial <span class="math-container">$p_\tau(x,y)=\sum\limits_{i,j}x^iy^j\tau_{i,j}$</span> and saying that since it is a non-zero polynomial of low degree at most <span class="math-container">$c\sqrt{n}$</span> it attains each value of <span class="math-container">$\mathbb{F}_{2^\ell}$</span> with multiplicity at most <span class="math-container">$c\sqrt{n}2^\ell$</span> (from Schwartz-Zippel), so 
<span class="math-container">$$\forall\alpha\in\mathbb{F}_{2^\ell}:\Pr\limits_{x,y\in\mathbb{F}_{2^\ell}}[p_\tau(x,y)=\alpha]\leq c\sqrt{n}/2^\ell$$</span></p>

<p>I want to use it but I am stuck..., maybe we can say that the distribution of <span class="math-container">$p_\tau(x,y)$</span> is close enough to <span class="math-container">$U_{\mathbb{F}_{2^\ell}}$</span> in statistical distance in order to infer that the expeced value of <span class="math-container">$f_z(p_\tau(x,y))$</span> is close enough to <span class="math-container">$1/2$</span>?</p>

CC BY-SA 4.0
2019-01-14T22:58:53.893Z
Your notation is a bit strange to me. What the heck is a non-empty test $\tau$?  A vector of nonzero hamming weight? And, what is your final goal, what's the upper bound you need in your last equation?
kodlu
CC BY-SA 4.0
2019-01-15T10:51:09.650Z
@kodlu $\varepsilon$-biased distributions "fool" linear tests. Forget about the terminology "test", $\tau$ is just a vector in $\{0,1\}^n$ such that not all of its entries are $0$ (otherwise it is clear that the target expected value is not upper bounded by $\varepsilon$ but in fact is equal to $1$).
user621824
<derandomization><pseudorandomness>
Algebraic construction of $\varepsilon$-biased sets
user621824
# Algebraic construction of $\varepsilon$-biased sets

(Asked by: username_0 on 2019-01-14)

Let $\ell> 1$ be an integer and consider the mapping $\text{Tr}:\mathbb{F}\_{2^\ell}\to\mathbb{F}\_{2^\ell}$ defined by
$$\text{Tr}(x)=x^{2^0}+x^{2^{1}}+\cdots+x^{2^{\ell-1}}$$
It is then possible to show the following

1. $\text{Tr}$ maps $\mathbb{F}\_{2^\ell}$ into $\mathbb{F}\_2$.
2. If $a\in\mathbb{F}\_{2^\ell}$ is non-zero, then the mapping $f\_a:\mathbb{F}\_{2^\ell}\to\mathbb{F}\_{2}$ defined by $f\_a(x)=\text{Tr}(a\cdot x)$ is $\mathbb{F}\_2$-linear and $\mathbb{E}\_{x\sim\mathbb{F}\_{2^\ell}}[f(x)]=\frac{1}{2}$.

Now, we consider the set $S=\{s(x,y,z):x,y,z\in\mathbb{F}\_{2^\ell}\}$ such that we index the entries of $s(x,y,z)$ by $0\leq i,j$ such that $i+j\leq c\sqrt{n}$ ($c$ is a constant so that there are exactly $n$ entries). For such $x,y,z$ and $i,j$ we set $s(x,y,z)\_{i,j}=\text{Tr}(x^iy^jz)$.

I want to show that for an appropriate choice of $\ell$, the set $S$ described above is an $\varepsilon$-biased set of size $O(n\sqrt{n}/\varepsilon^3)$.

Fix $\vec{0}\neq \tau\in\{0,1\}^n$, **what we need to show** is that (under good choice of $\ell$)
$$\bigg|\mathbb{E}\_{s\in S}\Big[(-1)^{\langle s,\tau\rangle}\Big]\bigg|\leq \varepsilon$$

Let $x,y,z\in\mathbb{F}\_{2^\ell}$ and consider $\langle s(x,y,z),\tau\rangle$, I managed to show that (from $\mathbb{F}\_2$-linearity above while indexing $\tau$ as we index $s(x,y,z)$)
$$\langle s(x,y,z),\tau\rangle=\cdots=f\_z\Big(\sum\_{i,j}x^iy^j\tau\_{i,j}\Big)$$
Finally, I thought of defining the bi-variate polynomial $p\_\tau(x,y)=\sum\limits\_{i,j}x^iy^j\tau\_{i,j}$ and saying that since it is a non-zero polynomial of low degree at most $c\sqrt{n}$ it attains each value of $\mathbb{F}\_{2^\ell}$ with multiplicity at most $c\sqrt{n}2^\ell$ (from Schwartz-Zippel), so
$$\forall\alpha\in\mathbb{F}\_{2^\ell}:\Pr\limits\_{x,y\in\mathbb{F}\_{2^\ell}}[p\_\tau(x,y)=\alpha]\leq c\sqrt{n}/2^\ell$$

I want to use it but I am stuck..., maybe we can say that the distribution of $p\_\tau(x,y)$ is close enough to $U\_{\mathbb{F}\_{2^\ell}}$ in statistical distance in order to infer that the expeced value of $f\_z(p\_\tau(x,y))$ is close enough to $1/2$?

**Tags:** derandomization, pseudorandomness
> **Comments:**
> **username_1**: Your notation is a bit strange to me. What the heck is a non-empty test $\tau$?  A vector of nonzero hamming weight? And, what is your final goal, what's the upper bound you need in your last equation?  
> **username_0**: @kodlu $\varepsilon$-biased distributions "fool" linear tests. Forget about the terminology "test", $\tau$ is just a vector in $\{0,1\}^n$ such that not all of its entries are $0$ (otherwise it is clear that the target expected value is not upper bounded by $\varepsilon$ but in fact is equal to $1$).  

---

## 1 answers

### Answer by username_0 on 2019-01-17. Score: 1 | Accepted answer

recall that
$$\langle s(x,y,z),\tau\rangle=\cdots=f\_z\Big(\sum\_{i,j}x^iy^j\tau\_{i,j}\Big)$$

if we define $p\_\tau(x,y)=\sum\limits\_{i,j}x^iy^j\tau\_{i,j}$, we have

$$\langle s(x,y,z),\tau\rangle=f\_{p\_\tau(x,y)}(z)$$

So, observe that whenever $p\_\tau(x,y)\neq 0$ we **win** as $z$ is uniform and the expected value of $f\_{p\_\tau(x,y)}(z)$ is also $1/2$ which means that the contribution to the bias of these $x,y$ is zero.

Again from Schwartz-Zippel we have only $O(\sqrt{n}/2^\ell)$ many zeros of $p\_\tau$ on them we lose the entire bias. So, the total bias is at most $O(\sqrt{n}/2^\ell)\stackrel{?}{\leq}\varepsilon$. Choosing $\ell=\Omega(\log(\sqrt{n}/\varepsilon))$ finishes the construction.


---

