Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR12-183 | 17th April 2013 16:53

#### Streaming bounds from difference ramification

Revision #1
Authors: András Salamon
Accepted on: 17th April 2013 16:53
Keywords:

Abstract:

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.

Changes to previous version:

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.

### Paper:

TR12-183 | 25th December 2012 16:23

#### Streaming bounds from difference ramification

TR12-183
Authors: András Salamon
Publication: 26th December 2012 15:06
Keywords:

Abstract:

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.

### Comment(s):

Comment #1 to TR12-183 | 17th April 2013 17:15

#### Note: this is a Myhill-Nerode style argument

Authors: András Salamon
Accepted on: 17th April 2013 17:15
Keywords:

Comment:

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.

ISSN 1433-8092 | Imprint