License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.70
URN: urn:nbn:de:0030-drops-112856
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11285/
Go to the corresponding LIPIcs Volume Portal

Chakrabarti, Amit ; Ghosh, Prantar

Streaming Verification of Graph Computations via Graph Structure

pdf-format:
LIPIcs-APPROX-RANDOM-2019-70.pdf (0.6 MB)

Abstract

We give new algorithms in the annotated data streaming setting - also known as verifiable data stream computation - for certain graph problems. This setting is meant to model outsourced computation, where a space-bounded verifier limited to sequential data access seeks to overcome its computational limitations by engaging a powerful prover, without needing to trust the prover. As is well established, several problems that admit no sublinear-space algorithms under traditional streaming do allow protocols using a sublinear amount of prover/verifier communication and sublinear-space verification. We give algorithms for many well-studied graph problems including triangle counting, its generalization to subgraph counting, maximum matching, problems about the existence (or not) of short paths, finding the shortest path between two vertices, and testing for an independent set. While some of these problems have been studied before, our results achieve new tradeoffs between space and communication costs that were hitherto unknown. In particular, two of our results disprove explicit conjectures of Thaler (ICALP, 2016) by giving triangle counting and maximum matching algorithms for n-vertex graphs, using o(n) space and o(n^2) communication.

BibTeX - Entry

@InProceedings{chakrabarti_et_al:LIPIcs:2019:11285,
  author =	{Amit Chakrabarti and Prantar Ghosh},
  title =	{{Streaming Verification of Graph Computations via Graph Structure}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{70:1--70:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11285},
  URN =		{urn:nbn:de:0030-drops-112856},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.70},
  annote =	{Keywords: data streams, interactive proofs, Arthur-Merlin, graph algorithms}
}

Keywords: data streams, interactive proofs, Arthur-Merlin, graph algorithms
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Issue Date: 2019
Date of publication: 17.09.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI