Abstract
Let D be a bwise 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: {0,1}^m > [1,1] are epsilonfooled by D+E, i.e., E[f(D+E)]  E[f(U)] <= epsilon where U is the uniform distribution.
We show that D+E epsilonfools product tests f: ({0,1}^n)^k > [1,1] given by the product of k bounded functions on disjoint nbit inputs with error epsilon = k(1eta)^{Omega(b^2/m)}, where m = nk and b >= n. This bound is tight when b = Omega(m) and eta >= (log k)/m. For b >= m^{2/3} log m and any constant eta the distribution D+E also 0.1fools logspace 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 ReedSolomon 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 epsilonfool product tests f: ({0,1}^n)^k > [1,1] under any permutation of the bits with seed lengths 2n + O~(k^2 log(1/epsilon)) and O(n) + O~(sqrt{nk log 1/epsilon}). Previous generators have seed lengths >= nk/2 or >= n sqrt{n k}. For the special case where the k bounded functions have range {0,1} the previous generators have seed length >= (n+log k)log(1/epsilon).
BibTeX  Entry
@InProceedings{haramaty_et_al:LIPIcs:2017:7518,
author = {Elad Haramaty and Chin Ho Lee and Emanuele Viola},
title = {{Bounded Independence Plus Noise Fools Products}},
booktitle = {32nd Computational Complexity Conference (CCC 2017)},
pages = {14:114:30},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770408},
ISSN = {18688969},
year = {2017},
volume = {79},
editor = {Ryan O'Donnell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7518},
URN = {urn:nbn:de:0030drops75188},
doi = {10.4230/LIPIcs.CCC.2017.14},
annote = {Keywords: ounded independence, Noise, Product tests, Errorcorrecting codes, Pseudorandomness}
}
Keywords: 

ounded independence, Noise, Product tests, Errorcorrecting codes, Pseudorandomness 
Collection: 

32nd Computational Complexity Conference (CCC 2017) 
Issue Date: 

2017 
Date of publication: 

01.08.2017 