TR16-169 Authors: Elad Haramaty, Chin Ho Lee, Emanuele Viola

Publication: 3rd November 2016 10:50

Downloads: 758

Keywords:

Let $D$ be a $b$-wise independent distribution over

$\{0,1\}^m$. Let $E$ be the ``noise'' distribution over

$\{0,1\}^m$ where the bits are independent and each bit is 1

with probability $\eta/2$. We study which tests $f \colon

\{0,1\}^m \to [-1,1]$ are $\e$-fooled by $D+E$, i.e.,

$|\E[f(D+E)] - \E[f(U)]| \le \e$ where $U$ is the uniform

distribution. We show that $D+E$ $\e$-fools product tests

$f : (\{0,1\}^n)^k \to [-1,1]$ given by the product of $k$

bounded functions on disjoint $n$-bit inputs with error

$\e = k(1-\eta)^{\Omega(b^2/m)}$, where $m = nk$ and $b

\ge n$. This bound is tight when $b = \Omega(m)$ and

$\eta \ge (\log k)/m$. For $b \ge m^{2/3} \log m$ and any

constant $\eta$ the distribution $D+E$ also $0.1$-fools

log-space algorithms.

We develop two applications of this type of results.

First, we prove communication lower bounds for decoding

noisy codewords of length $m$ split among $k$ parties.

For Reed--Solomon codes of dimension $m/k$ where $k =

O(1)$, communication $\Omega(\eta m) - O(\log m)$ is

required to decode one message symbol from a codeword

with $\eta m$ errors, and communication $O(\eta m \log

m)$ suffices. Second, we obtain pseudorandom generators.

We can $\e$-fool product tests $f\colon (\{0,1\}^n)^k \to

[-1,1]$ under any permutation of the bits with seed

lengths $2n + \tilde O(k^2 \log (1/\e))$ and $O(n) +

\tilde O(\sqrt{nk \log 1/\e})$. Previous generators had

seed lengths $\ge nk/2$ or $\ge n \sqrt{n k}$.