Abstract
We study graph computations in an enhanced data streaming setting, where a spacebounded 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 graphtheoretic 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 singlesource 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 nvertex 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
@InProceedings{chakrabarti_et_al:LIPIcs:2020:12625,
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:122:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771641},
ISSN = {18688969},
year = {2020},
volume = {176},
editor = {Jaros{\l}aw Byrka and Raghu Meka},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12625},
URN = {urn:nbn:de:0030drops126258},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.22},
annote = {Keywords: data streams, interactive proofs, ArthurMerlin, graph algorithms}
}
Keywords: 

data streams, interactive proofs, ArthurMerlin, graph algorithms 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) 
Issue Date: 

2020 
Date of publication: 

11.08.2020 