Invited to Theor. Comp. Sci. Journal (**TCS**)

Theory and App. of Models of Comp., (**TAMC**)

Theory and App. of Models of Comp., (

April, 2011

We study the complexity of the following problems in the streaming model. Membership testing for DLIN We show that every language in DLIN can be recognised by a randomized one-pass O(logn) space algorithm with inverse polynomial one-sided error, and by a deterministic p-pass O(n/p) space algorithm. We show that these algorithms are optimal.Membership testing for LL(k). For languages generated by LL(k) grammars with a bound of r on the number of nonterminals at any stage in the left-most derivation, we show that membership can be tested by a randomized one-pass O(rlogn) space algorithm with inverse polynomial (in n) one-sided error. Membership testing for DCFL We show that randomized algorithms as efficient as the ones described above for DLIN and $LL(k)$ (which are subclasses of DCFL) cannot exist for all of DCFL: there is a language in VPL (a subclass of DCFL) for which any randomized p-pass algorithm with error bounded by ϵ<1/2 must use Ω(n/p) space.Degree sequence problem We study the problem of determining, given a sequence d1,d2,…,dn and a graph G, whether the degree sequence of G is precisely d1,d2,…,dn. We give a randomized one-pass O(logn) space algorithm with inverse polynomial one-sided error probability. We show that our algorithms are optimal.Our randomized algorithms are based on the recent work of Magniez et al. cite{MMN09}; our lower bounds are obtained by considering related communication complexity problems.