Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

Streaming bounds from difference ramification

RSS-Feed




Revision #1
Authors: András Salamon
Accepted on: 17th April 2013 16:53
Downloads: 2457
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
Downloads: 2991
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