Document Open Access Logo

Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches

Authors Amit Chakrabarti , Prantar Ghosh, Justin Thaler

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2020.22.pdf
  • Filesize: 0.64 MB
  • 23 pages

Document Identifiers

Author Details

Amit Chakrabarti
  • Dartmouth College, Hanover, NH, USA
Prantar Ghosh
  • Dartmouth College, Hanover, NH, USA
Justin Thaler
  • Georgetown University, Washington, DC, USA

Funding

  • Chakrabarti, Amit: Work supported in part by NSF under award CCF-1907738.
  • Ghosh, Prantar: Work supported in part by NSF under award CCF-1907738.
  • Thaler, Justin: Work supported by NSF SPX award CCF-1918989, and NSF CAREER award CCF-1845125. Parts of this work were performed while visiting the Simons Institute for the Theory of Computing.

Cite As Get BibTex

Amit Chakrabarti, Prantar Ghosh, and Justin Thaler. Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 22:1-22:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.22

Abstract

We study graph computations in an enhanced data streaming setting, where a space-bounded client reading the edge stream of a massive graph may delegate some of its work to a cloud service. We seek algorithms that allow the client to verify a purported proof sent by the cloud service that the work done in the cloud is correct. A line of work starting with Chakrabarti et al. (ICALP 2009) has provided such algorithms, which we call schemes, for several statistical and graph-theoretic problems, many of which exhibit a tradeoff between the length of the proof and the space used by the streaming verifier.
This work designs new schemes for a number of basic graph problems - including triangle counting, maximum matching, topological sorting, and single-source shortest paths - where past work had either failed to obtain smooth tradeoffs between these two key complexity measures or only obtained suboptimal tradeoffs. Our key innovation is having the verifier compute certain nonlinear sketches of the input stream, leading to either new or improved tradeoffs. In many cases, our schemes in fact provide optimal tradeoffs up to logarithmic factors. 
Specifically, for most graph problems that we study, it is known that the product of the verifier’s space cost v and the proof length h must be at least Ω(n²) for n-vertex graphs. However, matching upper bounds are only known for a handful of settings of h and v on the curve h ⋅ v = Θ̃(n²). For example, for counting triangles and maximum matching, schemes with costs lying on this curve are only known for (h = Õ(n²), v = Õ(1)), (h = Õ(n), v = Õ(n)), and the trivial (h = Õ(1), v = Õ(n²)). A major message of this work is that by exploiting nonlinear sketches, a significant "portion" of costs on the tradeoff curve h ⋅ v = n² can be achieved.

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. 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
  2. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Analyzing graph structure via linear measurements. In Proc. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 459-467, 2012. 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, Yu Chen, and Sanjeev Khanna. Sublinear algorithms for (Δ+ 1) vertex coloring. In Proc. 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 767-786, 2019. Google Scholar
  6. 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
  7. 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
  8. 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
  9. J.A. Bondy and U.S.R Murty. Graph Theory. Springer Publishing Company, Incorporated, 1st edition, 2008. Google Scholar
  10. Luciana S. Buriol, Gereon Frahling, Stefano Leonardi, Alberto Marchetti-Spaccamela, and Christian Sohler. Counting triangles in data streams. In Proc. 25th ACM Symposium on Principles of Database Systems, pages 253-262, 2006. Google Scholar
  11. 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
  12. Amit Chakrabarti, Graham Cormode, Andrew McGregor, and Justin Thaler. Annotations in data streams. ACM Trans. Alg., 11(1):Article 7, 2014. Google Scholar
  13. 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
  14. Amit Chakrabarti and Prantar Ghosh. Streaming verification of graph computations via graph structure. In Proc. 33rd International Workshop on Randomization and Approximation Techniques in Computer Science, pages 70:1-70:20, 2019. Google Scholar
  15. Amit Chakrabarti, Prantar Ghosh, Andrew McGregor, and Sofya Vorotnikova. Vertex ordering problems in directed graph streams. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, pages 1786-1802, 2020. Google Scholar
  16. 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
  17. Graham Cormode, Jacques Dark, and Christian Konrad. Independent sets in vertex-arrival streams. In Proc. 46th International Colloquium on Automata, Languages and Programming, pages 45:1-45:14, 2019. Google Scholar
  18. Graham Cormode, Michael Mitzenmacher, and Justin Thaler. Streaming graph computations with a helpful advisor. Algorithmica, 65(2):409-442, 2013. Google Scholar
  19. Graham Cormode, Justin Thaler, and Ke Yi. Verifying computations with streaming interactive proofs. Proc. VLDB Endowment, 5(1):25-36, 2011. Google Scholar
  20. Alireza Farhadi, Mohammad Taghi Hajiaghayi, Tung Mai, Anup Rao, and Ryan A. Rossi. Approximate maximum matching in random streams. In Proc. 31st Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1773-1785, 2020. Google Scholar
  21. 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
  22. 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
  23. Tom Gur and Ran Raz. Arthur-Merlin streaming complexity. In Proc. 40th International Colloquium on Automata, Languages and Programming, pages 528-539, 2013. Google Scholar
  24. Madhav Jha, C. Seshadhri, and Ali Pinar. A space efficient streaming algorithm for triangle counting using the birthday paradox. In Proc. 19th Annual SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 589-597, 2013. Google Scholar
  25. Hossein Jowhari and Mohammad Ghodsi. New streaming algorithms for counting triangles in graphs. In Computing and Combinatorics, pages 710-716. Springer Berlin Heidelberg, 2005. Google Scholar
  26. John Kallaugher, Andrew McGregor, Eric Price, and Sofya Vorotnikova. The complexity of counting cycles in the adjacency list streaming model. In Proc. 38th ACM Symposium on Principles of Database Systems, pages 119-133, 2019. Google Scholar
  27. Daniel M. Kane, Kurt Mehlhorn, Thomas Sauerwald, and He Sun. Counting arbitrary subgraphs in data streams. In Automata, Languages, and Programming, pages 598-609. Springer Berlin Heidelberg, 2012. Google Scholar
  28. 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
  29. Michael Kapralov, Slobodan Mitrovic, Ashkan Norouzi-Fard, and Jakab Tardos. Space efficient approximation to maximum matching size from uniform edge samples. In Proc. 31st Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1753-1772, 2020. Google Scholar
  30. 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
  31. Mihail N. Kolountzakis, Gary L. Miller, Richard Peng, and Charalampos E. Tsourakakis. Efficient triangle counting in large graphs via degree-based vertex partitioning. Internet Mathematics, 8(1-2):161-185, 2012. Google Scholar
  32. 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
  33. 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
  34. Andrew McGregor, Sofya Vorotnikova, and Hoa T. Vu. Better algorithms for counting triangles in data streams. In Proc. 35th ACM Symposium on Principles of Database Systems, pages 401-411, 2016. Google Scholar
  35. Michael Mitzenmacher and Justin Thaler. Technical perspective: Catching lies (and mistakes) in offloaded computation. Commun. ACM, 59(2):102, 2016. Google Scholar
  36. Adi Shamir. IP = PSPACE. J. ACM, 39(4):869-877, 1992. Google Scholar
  37. Justin Thaler. Data stream verification. In Encyclopedia of Algorithms, pages 494-499. Springer Berlin Heidelberg, 2016. Google Scholar
  38. 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
  39. Peter A. Tucker, David Maier, Lois M. L. Delcambre, Tim Sheard, Jennifer Widom, and Mark P. Jones. Punctuated data streams, 2005. Google Scholar
  40. Douglas B. West. Introduction to Graph Theory. Prentice Hall, 2nd edition, 2001. Google Scholar
  41. Ke Yi, Feifei Li, Marios Hadjieleftheriou, George Kollios, and Divesh Srivastava. Randomized synopses for query assurance on data streams. In Proc. 24th International Conference on Data Engineering, pages 416-425, 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 About DROPS Imprint Privacy Contact