Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Abdullah, Amirali; Daruki, Samira; Roy, Chitradeep Dutta; Venkatasubramanian, Suresh http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-67730
URL:

; ; ;

Streaming Verification of Graph Properties

pdf-format:


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.

BibTeX - Entry

@InProceedings{abdullah_et_al:LIPIcs:2016:6773,
  author =	{Amirali Abdullah and Samira Daruki and Chitradeep Dutta Roy and Suresh Venkatasubramanian},
  title =	{{Streaming Verification of Graph Properties}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{3:1--3:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Seok-Hee Hong},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6773},
  URN =		{urn:nbn:de:0030-drops-67730},
  doi =		{10.4230/LIPIcs.ISAAC.2016.3},
  annote =	{Keywords: streaming interactive proofs, verification, matching, travelling salesman problem, graph algorithms}
}

Keywords: streaming interactive proofs, verification, matching, travelling salesman problem, graph algorithms
Seminar: 27th International Symposium on Algorithms and Computation (ISAAC 2016)
Issue date: 2016
Date of publication: 2016


DROPS-Home | Fulltext Search | Imprint Published by LZI