Kane, Daniel M.Nelson, JelaniWoodruff, David P.2015-01-232010Kane, Daniel M., Jelani Nelson, and David P. Woodruff. 2010. "On the Exact Space Complexity of Sketching and Streaming Small Norms." Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), January 17-19, 2010, Austin, Texas, ed. Moses Charikar: 1161-1178. Philadelphia, PA: Society for Industrial and Applied Mathematics.978-0-89871-701-3978-1-61197-307-5http://nrs.harvard.edu/urn-3:HUL.InstRepos:13820437We settle the 1-pass space complexity of \((1 \pm \epsilon)\)-approximating the \(L_p\) norm, for real p with 1 ≤ p ≤ 2, of a length-n vector updated in a length-m stream with updates to its coordinates. We assume the updates are integers in the range [–M, M]. In particular, we show the space required is \(\Theta(\epsilon^{−2} log(mM) + log log(n))\) bits. Our result also holds for 0 < p < 1; although \(L_p\) is not a norm in this case, it remains a well-defined function. Our upper bound improves upon previous algorithms of [Indyk, JACM ‘06] and [Li, SODA ‘08]. This improvement comes from showing an improved derandomization of the \(L_p\) sketch of Indyk by using k-wise independence for small k, as opposed to using the heavy hammer of a generic pseudorandom generator against space-bounded computation such as Nisan's PRG. Our lower bound improves upon previous work of [Alon-Matias-Szegedy, JCSS ‘99] and [Woodruff, SODA ‘04], and is based on showing a direct sum property for the 1-way communication of the gap-Hamming problem.en-USConference Paper2015-01-13Daniel M. Kane, Jelani Nelson, David P. Woodruff2015-01-2310.1137/1.9781611973075.93