In graph streaming a graph with $n$ vertices and $m$ edges is presented as a read-once stream of edges. We obtain an $\Omega(n \log n)$ streaming lower bound on the number of bits of space required to decide graph connectivity. This improves the known bound of $\Omega(n)$ bits, and matches the upper bound of $O(n \log n)$ bits. We go on to develop a method of ramifying inessential differences between streams into significant ones. For graph connectivity, this yields a crisp streaming lower bound (with no undetermined constants) of $n \log n - n(\log \log n + 3/2)$ bits, via lower bounds for the Bell numbers and a pigeonhole argument. We apply difference ramification to min-cut, for a crisp lower bound of $n(n-1)/2$ bits. Difference ramification also shows that streaming $n$-variable SAT requires at least $2^n$ bits, compared to the $O(n)$ bits that are sufficient for an unrestricted deterministic Turing machine.
Correct some claims about the Feigenbaum et al. directed bounds, corrected error in Bell number bound proof, added proofs and streaming SAT example. Reflecting submitted version for the record.
In graph streaming a graph with $n$ vertices and $m$ edges is presented as a read-once stream of edges. We obtain an $\Omega(n \log n)$ lower bound on the space required to decide graph connectivity. This improves the known bounds of $\Omega(n)$ for undirected and $\Omega(m)$ for sparse directed graphs. We develop a method of ramifying inessential differences into significant differences. For graph connectivity, this yields a crisp lower bound (with no undetermined constants) of $n \log n - n(\log \log n + 3/2)$ bits, via lower bounds for the Bell numbers and a pigeonhole argument. This lower bound is close to the $n\lceil\log n\rceil + 3\lceil\log n\rceil + \lceil\log \lceil\log n\rceil\rceil + c$ upper bound for an algorithm maintaining a disjoint-partition data structure, and which is therefore essentially optimal. We also apply difference ramification to min-cut, for a crisp lower bound of $n(n-1)/2$ bits.
An anonymous referee kindly pointed out that the Comparison Lemma is essentially a form of Myhill-Nerode argument, applied directly to streaming. I am leaving the paper up (in a corrected form), because the lower bounds themselves have not been published elsewhere and it may be useful to have them available for reference. The general idea of using Myhill-Nerode arguments in streaming otherwise appears to be sufficiently well established to feature in at least one undergraduate course, see http://www.stanford.edu/~rrwill/cs154-2013/notestream.pdf for the relevant online course notes.
