Document Open Access Logo

Streaming Verification of Graph Computations via Graph Structure

Authors Amit Chakrabarti , Prantar Ghosh

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2019.70.pdf
  • Filesize: 0.55 MB
  • 20 pages

Document Identifiers

Author Details

Amit Chakrabarti
  • Dartmouth College, Hanover, NH, USA
Prantar Ghosh
  • Dartmouth College, Hanover, NH, USA

Funding

This work was supported in part by NSF under award CCF-1907738.

Cite AsGet BibTex

Amit Chakrabarti and Prantar Ghosh. Streaming Verification of Graph Computations via Graph Structure. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 70:1-70:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.70

Abstract

We give new algorithms in the annotated data streaming setting - also known as verifiable data stream computation - for certain graph problems. This setting is meant to model outsourced computation, where a space-bounded verifier limited to sequential data access seeks to overcome its computational limitations by engaging a powerful prover, without needing to trust the prover. As is well established, several problems that admit no sublinear-space algorithms under traditional streaming do allow protocols using a sublinear amount of prover/verifier communication and sublinear-space verification. We give algorithms for many well-studied graph problems including triangle counting, its generalization to subgraph counting, maximum matching, problems about the existence (or not) of short paths, finding the shortest path between two vertices, and testing for an independent set. While some of these problems have been studied before, our results achieve new tradeoffs between space and communication costs that were hitherto unknown. In particular, two of our results disprove explicit conjectures of Thaler (ICALP, 2016) by giving triangle counting and maximum matching algorithms for n-vertex graphs, using o(n) space and o(n^2) communication.

Subject Classification

ACM Subject Classification
  • Theory of computation → Streaming models
  • Theory of computation → Interactive proof systems
  • Computer systems organization → Cloud computing
Keywords
  • data streams
  • interactive proofs
  • Arthur-Merlin
  • graph algorithms

Metrics

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

Related Versions

References

  1. Scott Aaronson and Avi Wigderson. Algebrization: A New Barrier in Complexity Theory. In Proc. 40th Annual ACM Symposium on the Theory of Computing, pages 731-740, 2008. Google Scholar
  2. Amirali Abdullah, Samira Daruki, Chitradeep Dutta Roy, and Suresh Venkatasubramanian. Streaming Verification of Graph Properties. In Proc. 27th International Symposium on Algorithms and Computation, pages 3:1-3:14, 2016. Google Scholar
  3. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof Verification and the Hardness of Approximation Problems. J. ACM, 45(3):501-555, 1998. Preliminary version in Proc. 33rd Annual IEEE Symposium on Foundations of Computer Science , pages 14-23, 1992. Google Scholar
  4. Sanjeev Arora and Shmuel Safra. Probabilistic Checking of Proofs: A New Characterization of NP. J. ACM, 45(1):70-122, 1998. Preliminary version in Proc. 33rd Annual IEEE Symposium on Foundations of Computer Science , pages 2-13, 1992. Google Scholar
  5. Sepehr Assadi, Sanjeev Khanna, and Yang Li. On Estimating Maximum Matching Size in Graph Streams. In Proc. 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1723-1742, 2017. Google Scholar
  6. Ziv Bar-Yossef, Ravi Kumar, and D. Sivakumar. Reductions in Streaming Algorithms, with an Application to Counting Triangles in Graphs. In Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 623-632, 2002. Google Scholar
  7. Suman K. Bera and Amit Chakrabarti. Towards Tighter Space Bounds for Counting Triangles and Other Substructures in Graph Streams. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), pages 11:1-11:14, 2017. Google Scholar
  8. J.A. Bondy and U.S.R Murty. Graph Theory. Springer Publishing Company, Incorporated, 1st edition, 2008. Google Scholar
  9. Amit Chakrabarti, Graham Cormode, Navin Goyal, and Justin Thaler. Annotations for Sparse Data Streams. In Proc. 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 687-706, 2014. Google Scholar
  10. Amit Chakrabarti, Graham Cormode, Andrew McGregor, and Justin Thaler. Annotations in Data Streams. ACM Trans. Alg., 11(1):Article 7, 2014. Google Scholar
  11. Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, and Suresh Venkatasubramanian. Verifiable Stream Computation and Arthur-Merlin Communication. In Proc. 30th Annual IEEE Conference on Computational Complexity, pages 217-243, 2015. Google Scholar
  12. Amit Chakrabarti and Sagar Kale. Submodular maximization meets streaming: matchings, matroids, and more. Math. Program., 154(1-2):225-247, 2015. Preliminary version in Proc. 17th Conference on Integer Programming and Combinatorial Optimization , pages 210-221, 2014. Google Scholar
  13. Graham Cormode, Michael Mitzenmacher, and Justin Thaler. Streaming Graph Computations with a Helpful Advisor. Algorithmica, 65(2):409-442, 2013. Google Scholar
  14. Graham Cormode, Justin Thaler, and Ke Yi. Verifying Computations with Streaming Interactive Proofs. Proc. VLDB Endowment, 5(1):25-36, 2011. Google Scholar
  15. Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. Graph Distances in the Data-Stream Model. SIAM J. Comput., 38(6):1709-1727, 2008. Preliminary version in Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms , pages 745-754, 2005. Google Scholar
  16. Ashish Goel, Michael Kapralov, and Sanjeev Khanna. On the communication and streaming complexity of maximum bipartite matching. In Proc. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 468-485, 2012. Google Scholar
  17. Venkatesan Guruswami and Krzysztof Onak. Superlinear Lower Bounds for Multipass Graph Processing. Algorithmica, 76(3):654-683, November 2016. Google Scholar
  18. Madhav Jha, C. Seshadhri, and Ali Pinar. A space efficient streaming algorithm for triangle counting using the birthday paradox. In The 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2013. Google Scholar
  19. John Kallaugher, Andrew McGregor, Eric Price, and Sofya Vorotnikova. The Complexity of Counting Cycles in the Adjacency List Streaming Model. In Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 119-133, 2019. Google Scholar
  20. Daniel M. Kane, Kurt Mehlhorn, Thomas Sauerwald, and He Sun. Counting Arbitrary Subgraphs in Data Streams. In Automata, Languages, and Programming - 39th International Colloquium, Proceedings, Part II, pages 598-609, 2012. Google Scholar
  21. Michael Kapralov. Better bounds for matchings in the streaming model. In Proc. 24th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1679-1697, 2013. Google Scholar
  22. Hartmut Klauck and Ved Prakash. Streaming computations with a loquacious prover. In Proc. 4th Conference on Innovations in Theoretical Computer Science, pages 305-320, 2013. Google Scholar
  23. Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan. Algebraic Methods for Interactive Proof Systems. J. ACM, 39(4):859-868, 1992. Google Scholar
  24. Andrew McGregor. Finding Graph Matchings in Data Streams. In Proc. 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pages 170-181, 2005. Google Scholar
  25. Andrew McGregor, Sofya Vorotnikova, and Hoa T. Vu. Better Algorithms for Counting Triangles in Data Streams. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS '16, pages 401-411, 2016. Google Scholar
  26. Michael Mitzenmacher and Justin Thaler. Technical Perspective: Catching lies (and mistakes) in offloaded computation. Commun. ACM, 59(2):102, 2016. Google Scholar
  27. Alexander Razborov. On the Distributional Complexity of Disjointness. Theor. Comput. Sci., 106(2):385-390, 1992. Preliminary version in Proc. 17th International Colloquium on Automata, Languages and Programming , pages 249-253, 1990. Google Scholar
  28. Adi Shamir. IP = PSPACE. J. ACM, 39(4):869-877, 1992. Google Scholar
  29. Justin Thaler. Semi-Streaming Algorithms for Annotated Graph Streams. In Proc. 43rd International Colloquium on Automata, Languages and Programming, pages 59:1-59:14, 2016. Google Scholar
  30. Peter A. Tucker, David Maier, Lois M. L. Delcambre, Tim Sheard, Jennifer Widom, and Mark P. Jones. Punctuated Data Streams, 2005. Google Scholar
  31. Ke Yi, Feifei Li, Marios Hadjieleftheriou, George Kollios, and Divesh Srivastava. Randomized Synopses for Query Assurance on Data Streams. In International Conference on Data Engineering, 2008. 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 Imprint Privacy Contact