Document Open Access Logo

Streaming Verification of Graph Properties

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

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2016.3.pdf
  • Filesize: 0.74 MB
  • 14 pages

Document Identifiers

Author Details

Amirali Abdullah
Samira Daruki
Chitradeep Dutta Roy
Suresh Venkatasubramanian

Cite As Get BibTex

Amirali Abdullah, Samira Daruki, Chitradeep Dutta Roy, and Suresh Venkatasubramanian. Streaming Verification of Graph Properties. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ISAAC.2016.3

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.

Subject Classification

Keywords
  • streaming interactive proofs
  • verification
  • matching
  • travelling salesman problem
  • graph algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. A. Abdullah, S. Daruki, C. D. Roy, and S. Venkatasubramanian. Streaming verification of graph properties. CoRR, abs/1602.08162, 2016. URL: http://arxiv.org/abs/1602.08162.
  2. Kook Jin Ahn and Sudipto Guha. Access to data and number of iterations: Dual primal algorithms for maximum matching under resource constraints. arXiv preprint arXiv:1307.4359, 2013. Google Scholar
  3. Kook Jin Ahn and Sudipto Guha. Linear programming in the semi-streaming model with application to the maximum matching problem. Information and Computation, 222:59-79, 2013. Google Scholar
  4. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Analyzing graph structure via linear measurements. In SODA, pages 459-467. SIAM, 2012. Google Scholar
  5. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Graph sketches: sparsification, spanners, and subgraphs. In Proceedings of the 31st Symposium on Principles of Database Systems, pages 5-14. ACM, 2012. Google Scholar
  6. Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009. Google Scholar
  7. Sepehr Assadi, Sanjeev Khanna, Yang Li, and Grigory Yaroslavtsev. Tight bounds for linear sketches of approximate matchings. arXiv preprint arXiv:1505.01467, 2015. Google Scholar
  8. Pablo Daniel Azar and Silvio Micali. Rational proofs. In STOC, pages 1017-1028. ACM, 2012. Google Scholar
  9. Bahman Bahmani, Ravi Kumar, and Sergei Vassilvitskii. Densest subgraph in streaming and mapreduce. Proceedings of the VLDB Endowment, 5(5):454-465, 2012. Google Scholar
  10. Ziv Bar-Yossef. The complexity of massive data set computations. PhD thesis, University of California at Berkeley, 2002. Google Scholar
  11. Ziv Bar-Yossef, Ravi Kumar, and D. Sivakumar. Reductions in streaming algorithms, with an application to counting triangles in graphs. In SODA, pages 623-632. Society for Industrial and Applied Mathematics, 2002. Google Scholar
  12. C. Berge. Sur le couplage maximum d'un graphe. Comptes rendus hebdomadaires des séances de l'Académie des sciences, 247:258-259, 1958. Google Scholar
  13. Vladimir Braverman, Rafail Ostrovsky, and Dan Vilenchik. How hard is counting triangles in the streaming model? In Automata, Languages, and Programming, pages 244-254. Springer, 2013. Google Scholar
  14. Luciana S Buriol, Gereon Frahling, Stefano Leonardi, Alberto Marchetti-Spaccamela, and Christian Sohler. Counting triangles in data streams. In Proceedings of the 25th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pages 253-262. ACM, 2006. Google Scholar
  15. Marc Bury and Chris Schwiegelshohn. Sublinear estimation of weighted matchings in dynamic data streams. arXiv preprint arXiv:1505.02019, 2015. Google Scholar
  16. Amit Chakrabarti, Graham Cormode, and Andrew McGregor. Annotations in data streams. In Automata, Languages and Programming, pages 222-234. Springer, 2009. Google Scholar
  17. Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, and Suresh Venkatasubramanian. Verifiable stream computation and arthur-merlin communication. In CCC, 2015. Google Scholar
  18. Bernard Chazelle, Ronitt Rubinfeld, and Luca Trevisan. Approximating the minimum spanning tree weight in sublinear time. SIAM Journal on Computing, 34(6):1370-1379, 2005. Google Scholar
  19. Jing Chen, Samuel McCauley, and Shikha Singh. Rational proofs with multiple provers. CoRR, abs/1504.08361, 2015. URL: http://arxiv.org/abs/1504.08361.
  20. Rajesh Chitnis, Graham Cormode, MohammadTaghi Hajiaghayi, and Morteza Monemizadeh. Parameterized streaming: maximal matching and vertex cover. In SODA, pages 1234-1251. SIAM, 2015. Google Scholar
  21. Graham Cormode. Bertinoro workshop 2011, problem 47. URL: http://sublinear.info/index.php?title=Open_Problems:47.
  22. Graham Cormode, Michael Mitzenmacher, and Justin Thaler. Streaming graph computations with a helpful advisor. Algorithmica, 65(2):409-442, 2013. Google Scholar
  23. Graham Cormode, Justin Thaler, and Ke Yi. Verifying computations with streaming interactive proofs. Proceedings of the VLDB Endowment, 5(1):25-36, 2011. Google Scholar
  24. Michael Crouch and Daniel M. Stubbs. Improved streaming algorithms for weighted matching, via unweighted matching. APPROX/RANDOM, 28:96-104, 2014. Google Scholar
  25. W. H. Cunningham and A. B. Marsh. A primal algorithm for optimum matching. In Polyhedral Combinatorics, pages 50-72. Springer, 1978. Google Scholar
  26. Samira Daruki, Justin Thaler, and Suresh Venkatasubramanian. Streaming verification in data analysis. In Algorithms and Computation, pages 715-726. Springer Berlin Heidelberg, 2015. Google Scholar
  27. Leah Epstein, Asaf Levin, Julián Mestre, and Danny Segev. Improved approximation guarantees for weighted matching in the semi-streaming model. SIAM Journal on Discrete Mathematics, 25(3):1251-1265, 2011. Google Scholar
  28. Hossein Esfandiari, Mohammad T Hajiaghayi, Vahid Liaghat, Morteza Monemizadeh, and Krzysztof Onak. Streaming algorithms for estimating the matching size in planar graphs and beyond. In SODA, pages 1217-1233. SIAM, 2015. Google Scholar
  29. Stephen A. Fenner, Rohit Gurjar, and Thomas Thierauf. Bipartite perfect matching is in quasi-nc. Electronic Colloquium on Computational Complexity (ECCC), 22:177, 2015. URL: http://eccc.hpi-web.de/report/2015/177.
  30. Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. Delegating computation: Interactive proofs for muggles. In STOC'08, pages 113-122, New York, NY, USA, 2008. ACM. Google Scholar
  31. Siyao Guo, Pavel Hubáček, Alon Rosen, and Margarita Vald. Rational arguments: single round delegation with sublinear verification. In Proc. ITCS, pages 523-540. ACM, 2014. Google Scholar
  32. Siyao Guo, Pavel Hubáček, Alon Rosen, and Margarita Vald. Rational sumchecks. In Theory of Cryptography, pages 319-351. Springer, 2016. Google Scholar
  33. Tom Gur and Ron D. Rothblum. Non-interactive proofs of proximity. In Tim Roughgarden, editor, Proc. ITCS, pages 133-142. ACM, 2015. Google Scholar
  34. Hossein Jowhari and Mohammad Ghodsi. New streaming algorithms for counting triangles in graphs. In Computing and Combinatorics, pages 710-716. Springer, 2005. Google Scholar
  35. Yael Tauman Kalai, Ran Raz, and Ron D. Rothblum. How to delegate computations: The power of no-signaling proofs. Cryptology ePrint Archive, Report 2013/862, 2013. URL: http://eprint.iacr.org/.
  36. Michael Kapralov. Better bounds for matchings in the streaming model. In SODA, pages 1679-1697. SIAM, 2013. Google Scholar
  37. R. M. Karp, E. Upfal, and A. Wigderson. Constructing a perfect matching is in random NC. Combinatorica, 6(1):35-48, January 1986. Google Scholar
  38. Hartmut Klauck. On arthur merlin games in communication complexity. In Computational Complexity (CCC), 2011 IEEE 26th Annual Conference on, pages 189-199. IEEE, 2011. Google Scholar
  39. Hartmut Klauck and Ved Prakash. An improved interactive streaming algorithm for the distinct elements problem. In Automata, Languages, and Programming, pages 919-930. Springer, 2014. Google Scholar
  40. Dmitry Kogan and Robert Krauthgamer. Sketching cuts in graphs and hypergraphs. In Proc. ITCS, pages 367-376. ACM, 2015. Google Scholar
  41. D. König. Gráfok és alkalmazásuk a determinánsok és a halmazok elméletére. Matematikai és Természettudományi Értesítǒ, 34:104-119, 1916. Google Scholar
  42. Christian Konrad. Maximum matching in turnstile streams. arXiv preprint arXiv:1505.01460, 2015. Google Scholar
  43. Andrew McGregor. Graph stream algorithms: A survey. ACM SIGMOD Record, 43(1):9-20, 2014. Google Scholar
  44. Aduri Pavan, Kanat Tangwongsan, Srikanta Tirthapura, and Kun-Lung Wu. Counting and sampling triangles from a graph stream. Proceedings of the VLDB Endowment, 6(14):1870-1881, 2013. Google Scholar
  45. Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. Constant-round interactive proofs for delegating computation. In Proc. STOC, 2016. Google Scholar
  46. Christian Sohler. Dortmund workshop on streaming algorithms, problem 52. 2012. URL: http://sublinear.info/index.php?title=Open_Problems:52.
  47. Justin Thaler. Semi-streaming algorithms for annotated graph streams. In Proc. ICALP, 2016. Google Scholar
  48. W. T. Tutte. The factorization of linear graphs. The Journal of the London Mathematical Society, Ser. 1, 22(2):107-111, 1947. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact