Promised streaming algorithms and finding pseudo-repetitions

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.