3
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – kodlu Jan 14 at 22:58
  • $\begingroup$ @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$). $\endgroup$ – user621824 Jan 15 at 10:51
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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