Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR16-169 | 3rd November 2016 10:50

Bounded independence plus noise fools products


Authors: Elad Haramaty, Chin Ho Lee, Emanuele Viola
Publication: 3rd November 2016 10:50
Downloads: 592


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}$.

ISSN 1433-8092 | Imprint