Streaming verification of graph properties

DOI10.4230/LIPICS.ISAAC.2016.3MaRDI QIDQ4636484zbMATHOpenAlexFDO

Authors Amirali Abdullah, Samira Daruki, Chitradeep Dutta Roy, Suresh Venkatasubramanian

Publication date 19 April 2018

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

zbMATH Keywords

verificationmatchinggraph algorithmstravelling salesman problemstreaming interactive proofs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Streaming interactive proofs (SIPs) are a framework for outsourced computation. A computationally limited streaming client (the verifier) hands over a large data set to an untrusted server (the prover) in the cloud and the two parties run a protocol to confirm the correctness of result with high probability. SIPs are particularly interesting for problems that are hard to solve (or even approximate) well in a streaming setting. The most notable of these problems is finding maximum matchings, which has received intense interest in recent years but has strong lower bounds even for constant factor approximations. In this paper, we present efficient streaming interactive proofs that can verify maximum matchings exactly. Our results cover all flavors of matchings (bipartite/non-bipartite and weighted). In addition, we also present streaming verifiers for approximate metric TSP. In particular, these are the first efficient results for weighted matchings and for metric TSP in any streaming verification model.

Recommendations

• Streaming Verification in Data Analysis
• scientific article; zbMATH DE number 6829278
• Verifiable stream computation and Arthur-Merlin communication
• Best-Order Streaming Model
• Practical verified computation with streaming interactive proofs

Cited in

(6)

• Streaming Verification in Data Analysis
• scientific article; zbMATH DE number 7650137 (Why is no real title available?)
• Best-Order Streaming Model
• scientific article; zbMATH DE number 7758324 (Why is no real title available?)
• Verifiable stream computation and Arthur-Merlin communication
• Best-order streaming model

This page was built for publication: Streaming verification of graph properties

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