Tight bounds for data stream algorithms and communication problems
Mert Sağlam · Summit (Simon Fraser University) · 2011
In this thesis, we give efficient algorithms and near-tight lower bounds for the following problems in the streaming model. Improving on the works of Monemizadeh and Woodruff from SODA'10 and Andoni, Krauthgamer and Onak from FOCS'11, we give $L_p$-samplers requiring $O(epsilon^{-p}log^2n)$ space for $pin(1,2)$. Our algorithm also works for $pin[0,1]$, taking $tilde{O}(epsilon^{-1}log^2n)$ space. As an application of our sampler, we give an $O(log^2n)$ space algorithm for finding duplicates in data streams, improving the algorithms of Gopalan and Radhakrishnan from SODA'09. Given a stream that consists of a pattern of length $m$ and a text of length $n$, the pattern matching problem is to output all occurrences of the pattern. Improving on the results of Porat and Porat from FOCS'09, we give a $O(log{}nlog{}m)$ space algorithm that works entirely in the streaming model. Finally we show several near-tight lower bounds for the above problems through new results in communication complexity.