2014/04/04 by Glencora Borradaile, Borradaile, Glencora, Claire Mathieu +3
Computer Science · #Complexity and Algorithms in Graphs #Privacy-Preserving Technologies in Data #Stochastic Gradient Optimization Techniques #cs.CC #cs.DS
paper · pdf · doi:10.48550/arxiv.1404.1323
Added some references to previous work, removed the part of the result that was already known before, and changed the label of the result from "Theorem" to "Lemma"
arxiv created 2014/04/08 · arxiv updated 2014/04/09
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 Ω(εm) on a graph with m edges to be determined correctly with probability greater than (1+ε)/2.