Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > TOPOLOGICAL SORT:
Reports tagged with topological sort:
TR20-100 | 6th July 2020
Amit Chakrabarti, Prantar Ghosh, Justin Thaler

Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches

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 ... more >>>




ISSN 1433-8092 | Imprint