Thaler, Justin
SemiStreaming Algorithms for Annotated Graph Streams
Abstract
Considerable effort has been devoted to the development of streaming algorithms for analyzing massive graphs. Unfortunately, many results have been negative, establishing that a wide variety of problems require Omega(n^2) space to solve. One of the few bright spots has been the development of semistreaming algorithms for a handful of graph problems  these algorithms use space O(n*polylog(n)).
In the annotated data streaming model of Chakrabarti et al. [Chakrabarti/Cormode/Goyal/Thaler, ACM Trans. on Alg. 2014], a computationally limited client wants to compute some property of a massive input, but lacks the resources to store even a small fraction of the input, and hence cannot perform the desired computation locally. The client therefore accesses a powerful but untrusted service provider, who not only performs the requested computation, but also proves that the answer is correct.
We consider the notion of semistreaming algorithms for annotated graph streams (semistreaming annotation schemes for short). These are protocols in which both the client's space usage and the length of the proof are O(n*polylog(n)). We give evidence that semistreaming annotation schemes represent a more robust solution concept than does the standard semistreaming model. On the positive side, we give semistreaming annotation schemes for two dynamic graph problems that are intractable in the standard model: (exactly) counting triangles, and (exactly) computing maximum matchings. The former scheme answers a question of Cormode [Cormode, Problem 47]. On the negative side, we identify for the first time two natural graph problems (connectivity and bipartiteness in a certain edge update model) that can be solved in the standard semistreaming model, but cannot be solved by annotation schemes of "subsemistreaming" cost. That is, these problems are as hard in the annotations model as they are in the standard model.
BibTeX  Entry
@InProceedings{thaler:LIPIcs:2016:6224,
author = {Justin Thaler},
title = {{SemiStreaming Algorithms for Annotated Graph Streams}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {59:159:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770132},
ISSN = {18688969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6224},
URN = {urn:nbn:de:0030drops62247},
doi = {10.4230/LIPIcs.ICALP.2016.59},
annote = {Keywords: graph streams, stream verification, annotated data streams, probabilistic proof systems}
}
23.08.2016
Keywords: 

graph streams, stream verification, annotated data streams, probabilistic proof systems 
Seminar: 

43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Issue date: 

2016 
Date of publication: 

23.08.2016 