Streaming verification of graph properties

DOI10.4230/LIPICS.ISAAC.2016.3zbMATH Open1398.68380arXiv1602.08162OpenAlexW2962941701MaRDI QIDQ4636484FDOQ4636484

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

Publication date: 19 April 2018

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.

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

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

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)

Cited In (6)

• Best-order streaming model
• Verifiable Stream Computation and Arthur--Merlin Communication
• Title not available (Why is that?)
• Title not available (Why is that?)
• Streaming Verification in Data Analysis
• 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)