Tight bounds for data stream algorithms and communication problems

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 $p\in(1,2)$. Our algorithm also works for $p\in[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{}n\log{}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.