Promised streaming algorithms and finding pseudo-repetitions
Promised streaming algorithms and finding pseudo-repetitions
Files
Publication or External Link
Date
2013
Authors
Tiseanu, Catalin Stefan
Advisor
Hajiaghayi, MohammadTaghi
Citation
DRUM DOI
Abstract
As the size of data available for processing increases, new models of
computation are needed. This motivates the study of data streams, which are sequences of
information for which each element can be read only after the previous one. In
this work we study two particular types of streaming variants: promised graph streaming algorithms and
combinatorial queries on large words. We give an &omega(n) lower
bound for working memory, where n is the number of vertices of the graph, for a variety
of problems for which the graphs are promised to be forests. The crux
of the proofs is based on reductions from the field of communication complexity.
Finally, we give an upper bound for two problems related to finding
pseudo-repetitions on words via anti-/morphisms, for which we also propose streaming versions.