Semi-streaming algorithms for annotated graph streams

DOI10.4230/LIPICS.ICALP.2016.59MaRDI QIDQ4598198zbMATH OpenOpenAlexFDO

Authors Justin Thaler

Publication date 19 December 2017

Full work available at URL https://arxiv.org/abs/1407.3462

zbMATH Keywords

annotated data streamsgraph streamsprobabilistic proof systemsstream verification

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

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 semi-streaming algorithms for a handful of graph problems -- these algorithms use space $O(ncdotextpolylog(n))$. In the annotated data streaming model of Chakrabarti et al., 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 put forth the notion of semi-streaming algorithms for annotated graph streams (semi-streaming annotation schemes for short). These are protocols in which both the client's space usage and the length of the proof are $O(ncdotextpolylog(n))$. We give evidence that semi-streaming annotation schemes represent a substantially more robust solution concept than does the standard semi-streaming model. On the positive side, we give semi-streaming 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. 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 semi-streaming model, but cannot be solved by annotation schemes of "sub-semi-streaming" cost. That is, these problems are just as hard in the annotations model as they are in the standard model.

Recommendations

• Automata, Languages and Programming
• On graph problems in a semi-streaming model
• Annotations in Data Streams
• Annotations for Sparse Data Streams

Cited in

(20)

• Non-interactive proofs of proximity
• An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity
• Labeled graph sketches: keeping up with real-time graph streams
• Optimal per-edge processing times in the semi-streaming model
• On graph problems in a semi-streaming model
• Annotations in Data Streams
• A hierarchy theorem for interactive proofs of proximity
• Annotations in data streams
• Simple doubly-efficient interactive proof systems for locally-characterizable sets
• An exponential separation between MA and AM proofs of proximity
• Optimality of linear sketching under modular updates
• scientific article; zbMATH DE number 7250148 (Why is no real title available?)
• A Survey of Graph Algorithms Under Extended Streaming Models of Computation
• Verifiable stream computation and Arthur-Merlin communication
• Annotations for Sparse Data Streams
• Automata, Languages and Programming
• Approximate F₂-Sketching of Valuation Functions
• scientific article; zbMATH DE number 7650137 (Why is no real title available?)
• scientific article; zbMATH DE number 7758324 (Why is no real title available?)
• New lower bounds in Merlin-Arthur communication and graph streaming verification

This page was built for publication: Semi-streaming algorithms for annotated graph streams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598198)