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/
Go to the corresponding LIPIcs Volume Portal

Haramaty, Elad ; Lee, Chin Ho ; Viola, Emanuele

Bounded Independence Plus Noise Fools Products

pdf-format:
LIPIcs-CCC-2017-14.pdf (0.6 MB)

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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI