License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2017.14
URN: urn:nbn:de:0030-drops-75188
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7518/
Haramaty, Elad ;
Lee, Chin Ho ;
Viola, Emanuele
Bounded Independence Plus Noise Fools Products
Abstract
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: {0,1}^m -> [-1,1] are epsilon-fooled by D+E, i.e., |E[f(D+E)] - E[f(U)]| <= epsilon where U is the uniform distribution.
We show that D+E epsilon-fools product tests f: ({0,1}^n)^k -> [-1,1] given by the product of k bounded functions on disjoint n-bit inputs with error epsilon = k(1-eta)^{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.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 epsilon-fool 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:1--14:30},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-040-8},
ISSN = {1868-8969},
year = {2017},
volume = {79},
editor = {Ryan O'Donnell},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7518},
URN = {urn:nbn:de:0030-drops-75188},
doi = {10.4230/LIPIcs.CCC.2017.14},
annote = {Keywords: ounded independence, Noise, Product tests, Error-correcting codes, Pseudorandomness}
}
Keywords: |
|
ounded independence, Noise, Product tests, Error-correcting codes, Pseudorandomness |
Collection: |
|
32nd Computational Complexity Conference (CCC 2017) |
Issue Date: |
|
2017 |
Date of publication: |
|
01.08.2017 |