ECCC-Report TR17-090https://eccc.weizmann.ac.il/report/2017/090Comments and Revisions published for TR17-090en-usMon, 15 May 2017 19:12:04 +0300
Paper TR17-090
| The coin problem for product tests |
Emanuele Viola,
Chin Ho Lee
https://eccc.weizmann.ac.il/report/2017/090Let $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.
Mon, 15 May 2017 19:12:04 +0300https://eccc.weizmann.ac.il/report/2017/090