%0 Journal Article
%T Lower bounds for testing digraph connectivity with one-pass streaming algorithms
%A Glencora Borradaile
%A Claire Mathieu
%A Theresa Migler
%J Computer Science
%D 2014
%I arXiv
%X In this note, we show that three graph properties - strong connectivity, acyclicity, and reachability from a vertex $s$ to all vertices - each require a working memory of $\Omega (\epsilon m)$ on a graph with $m$ edges to be determined correctly with probability greater than $(1+\epsilon)/2$.
%U http://arxiv.org/abs/1404.1323v2