TR17-090 Authors: Chin Ho Lee, Emanuele Viola

Publication: 15th May 2017 19:12

Downloads: 511

Keywords:

Let $X_{m, \eps}$ be the distribution over $m$ bits $(X_1, \ldots, X_m)$

where the $X_i$ are independent and each $X_i$ equals $1$ with

probability $(1+\eps)/2$ and $0$ with probability $(1-\eps)/2$. We

consider the smallest value $\eps^*$ of $\eps$ such that the distributions

$X_{m,\eps}$ and $X_{m,0}$ can be distinguished with constant

advantage by a function $f : \{0,1\}^m \to S$ which is the product of $k$

functions $f_1, f_2, \ldots, f_k$ on disjoint inputs of $n$ bits, where each

$f_i : \{0,1\}^n \to S$ and $m = nk$.

We prove that $\eps^* = \Theta(1/\sqrt{n \log k})$ if $S = \{0,1\}$ and if $S

= \{-1,1\}$, while $\eps^* = \Theta(1/\sqrt{nk})$ if $S$ is the set of

unit-norm complex numbers.