Robust characterizations of k‐wise independence over product spaces and related testing results123. Issue 3 (7th May 2012)

• Record Type: Journal Article
• Authors: Rubinfeld, Ronitt; Xie, Ning
• Is Part Of: Random structures & algorithms. Volume 43:Issue 3(2013)
• Page Start: 265
• Page End: 312
• Publication Date: 2012-05-07
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20423
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main" xml:lang="en"> <title>Abstract</title> <p>A discrete distribution <italic>D</italic> over Σ<sub>1</sub> ×··· ×Σ<sub><italic>n</italic></sub> is called <italic>(non‐uniform) k ‐wise independent</italic> if for any subset of <italic>k</italic> indices {<italic>i</italic><sub>1</sub>, …, <italic>i</italic><sub><italic>k</italic></sub>} and for any <italic>z</italic><sub>1</sub>∈Σ<mml:math overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mtext> </mml:mtext><mml:mrow><mml:mtext fontstyle="italic">i</mml:mtext><mml:msub><mml:mtext> </mml:mtext><mml:mrow><mml:mtext>1</mml:mtext></mml:mrow></mml:msub></mml:mrow></mml:msub></mml:math><inline-graphic xlink:href="ark:/27927/pgg2pr8dczw" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />, …, <italic>z</italic><sub><italic>k</italic></sub>∈Σ<mml:math overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mtext> </mml:mtext><mml:mrow><mml:mtext fontstyle="italic">i</mml:mtext><mml:msub><mml:mtext> </mml:mtext><mml:mrow><mml:mtext fontstyle="italic">k</mml:mtext></mml:mrow></mml:msub></mml:mrow></mml:msub></mml:math><inline-graphic xlink:href="ark:/27927/pgg2pr8dcws" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />, Pr<sub><italic>X</italic>∼<italic>D</italic></sub>[<italic>X</italic><mml:math overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mtext> </mml:mtext><mml:mrow><mml:mtext fontstyle="italic">i</mml:mtext><mml:msub><mml:mtext> </mml:mtext><mml:mrow><mml:mtext>1</mml:mtext></mml:mrow></mml:msub></mml:mrow></mml:msub></mml:math><inline-graphic xlink:href="ark:/27927/pgg2pr8d60v" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />···<italic>X</italic><mml:math overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mtext> </mml:mtext><mml:mrow><mml:mtext fontstyle="italic">i</mml:mtext><mml:msub><mml:mtext> </mml:mtext><mml:mrow><mml:mtext fontstyle="italic">k</mml:mtext></mml:mrow></mml:msub></mml:mrow></mml:msub></mml:math><inline-graphic xlink:href="ark:/27927/pgg2pr8d8f2" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> = <italic>z</italic><sub>1</sub>···<italic>z</italic><sub><italic>k</italic></sub>] = Pr<sub><italic>X</italic>∼<italic>D</italic></sub>[<italic>X</italic><mml:math overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mtext> </mml:mtext><mml:mrow><mml:mtext fontstyle="italic">i</mml:mtext><mml:msub><mml:mtext> </mml:mtext><mml:mrow><mml:mtext>1</mml:mtext></mml:mrow></mml:msub></mml:mrow></mml:msub></mml:math><inline-graphic xlink:href="ark:/27927/pgg2pr8d843" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> = <italic>z</italic><sub>1</sub>]···Pr<sub><italic>X</italic>∼<italic>D</italic></sub>[<italic>X</italic><mml:math overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mtext> </mml:mtext><mml:mrow><mml:mtext fontstyle="italic">i</mml:mtext><mml:msub><mml:mtext> </mml:mtext><mml:mrow><mml:mtext fontstyle="italic">k</mml:mtext></mml:mrow></mml:msub></mml:mrow></mml:msub></mml:math><inline-graphic xlink:href="ark:/27927/pgg2pr8d8vp" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> = <italic>z</italic><sub><italic>k</italic></sub>]. We study the problem of testing (non‐uniform) <italic>k</italic> ‐wise independent distributions over product spaces. For the uniform case we show an upper bound on the distance between a distribution <italic>D</italic> from <italic>k</italic> ‐wise independent distributions in terms of the sum of Fourier coefficients of <italic>D</italic> at vectors of weight at most <italic>k</italic>. Such a bound was previously known only when the underlying domain is {0, 1}<sup><italic>n</italic></sup>. For the non‐uniform case, we give a new characterization of distributions being <italic>k</italic> ‐wise independent and further show that such a characterization is robust based on our results for the uniform case. These results greatly generalize those of Alon et al. (STOC'07, pp. 496–505) on uniform <italic>k</italic> ‐wise independence over the Boolean cubes to non‐uniform <italic>k</italic> ‐wise independence over product spaces. Our results yield natural testing algorithms for <italic>k</italic> ‐wise independence with time and sample complexity sublinear in terms of the support size of the distribution when <italic>k</italic> is a constant. The main technical tools employed include discrete Fourier transform and the theory of linear systems of congruences.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013</p> </abstract>