Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR17-090 | 15th May 2017 19:11

The coin problem for product tests

TR17-090
Authors: Chin Ho Lee, Emanuele Viola
Publication: 15th May 2017 19:12
Keywords:

Abstract:

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.

ISSN 1433-8092 | Imprint