2026-08-17T07:51:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2449 2024-03-06T10:33:21Z ddc:004 open_access

AMS Without 4-Wise Independence on Product Domains Braverman, Vladimir Chung, Kai-Min Liu, Zhenming Mitzenmacher, Michael Ostrovsky, Rafail Data Streams Randomized Algorithms Streaming Algorithms Independence Sketches In their seminal work, Alon, Matias, and Szegedy introduced several sketching techniques, including showing that $4$-wise independence is sufficient to obtain good approximations of the second frequency moment. In this work, we show that their sketching technique can be extended to product domains $[n]^k$ by using the product of $4$-wise independent functions on $[n]$. Our work extends that of Indyk and McGregor, who showed the result for $k = 2$. Their primary motivation was the problem of identifying correlations in data streams. In their model, a stream of pairs $(i,j) \in [n]^2$ arrive, giving a joint distribution $(X,Y)$, and they find approximation algorithms for how close the joint distribution is to the product of the marginal distributions under various metrics, which naturally corresponds to how close $X$ and $Y$ are to being independent. By using our technique, we obtain a new result for the problem of approximating the $\ell_2$ distance between the joint distribution and the product of the marginal distributions for $k$-ary vectors, instead of just pairs, in a single pass. Our analysis gives a randomized algorithm that is a $(1\pm \epsilon)$ approximation (with probability $1-\delta$) that requires space logarithmic in $n$ and $m$ and proportional to $3^k$. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vladimir Braverman and Kai-Min Chung and Zhenming Liu and Michael Mitzenmacher and Rafail Ostrovsky 2010 Is Part Of LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2010.2449 urn:nbn:de:0030-drops-24496 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2449 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode