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.2020.22
URN: urn:nbn:de:0030-drops-126258
Go to the corresponding LIPIcs Volume Portal

Chakrabarti, Amit ; Ghosh, Prantar ; Thaler, Justin

Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches

LIPIcs-APPROX22.pdf (0.6 MB)


We study graph computations in an enhanced data streaming setting, where a space-bounded client reading the edge stream of a massive graph may delegate some of its work to a cloud service. We seek algorithms that allow the client to verify a purported proof sent by the cloud service that the work done in the cloud is correct. A line of work starting with Chakrabarti et al. (ICALP 2009) has provided such algorithms, which we call schemes, for several statistical and graph-theoretic problems, many of which exhibit a tradeoff between the length of the proof and the space used by the streaming verifier.
This work designs new schemes for a number of basic graph problems - including triangle counting, maximum matching, topological sorting, and single-source shortest paths - where past work had either failed to obtain smooth tradeoffs between these two key complexity measures or only obtained suboptimal tradeoffs. Our key innovation is having the verifier compute certain nonlinear sketches of the input stream, leading to either new or improved tradeoffs. In many cases, our schemes in fact provide optimal tradeoffs up to logarithmic factors.
Specifically, for most graph problems that we study, it is known that the product of the verifier’s space cost v and the proof length h must be at least Ω(n²) for n-vertex graphs. However, matching upper bounds are only known for a handful of settings of h and v on the curve h ⋅ v = Θ̃(n²). For example, for counting triangles and maximum matching, schemes with costs lying on this curve are only known for (h = Õ(n²), v = Õ(1)), (h = Õ(n), v = Õ(n)), and the trivial (h = Õ(1), v = Õ(n²)). A major message of this work is that by exploiting nonlinear sketches, a significant "portion" of costs on the tradeoff curve h ⋅ v = n² can be achieved.

BibTeX - Entry

  author =	{Amit Chakrabarti and Prantar Ghosh and Justin Thaler},
  title =	{{Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{22:1--22:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Jaros{\l}aw Byrka and Raghu Meka},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-126258},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.22},
  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 2020)
Issue Date: 2020
Date of publication: 11.08.2020

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