ECCC-Report TR12-183https://eccc.weizmann.ac.il/report/2012/183Comments and Revisions published for TR12-183en-usWed, 17 Apr 2013 17:15:28 +0300
Comment 1
| Note: this is a Myhill-Nerode style argument |
András Salamon
https://eccc.weizmann.ac.il/report/2012/183#comment1An 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.Wed, 17 Apr 2013 17:15:28 +0300https://eccc.weizmann.ac.il/report/2012/183#comment1
Revision 1
| Streaming bounds from difference ramification |
András Salamon
https://eccc.weizmann.ac.il/report/2012/183#revision1In 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.
Wed, 17 Apr 2013 16:53:51 +0300https://eccc.weizmann.ac.il/report/2012/183#revision1
Paper TR12-183
| Streaming bounds from difference ramification |
András Salamon
https://eccc.weizmann.ac.il/report/2012/183In 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.
Wed, 26 Dec 2012 15:06:24 +0200https://eccc.weizmann.ac.il/report/2012/183