Document Open Access Logo

Adversarially Robust Coloring for Graph Streams

Authors Amit Chakrabarti , Prantar Ghosh, Manuel Stoeckl

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.37.pdf
  • Filesize: 0.89 MB
  • 23 pages

Document Identifiers

Author Details

Amit Chakrabarti
  • Department of Computer Science, Dartmouth College, Hanover, NH, USA
Prantar Ghosh
  • Department of Computer Science, Dartmouth College, Hanover, NH, USA
Manuel Stoeckl
  • Department of Computer Science, Dartmouth College, Hanover, NH, USA

Funding

This work was supported in part by NSF under awards 1907738 and 2006589.

Acknowledgements

Prantar Ghosh would like to thank Sayan Bhattacharya for a helpful conversation regarding this work.

Cite As Get BibTex

Amit Chakrabarti, Prantar Ghosh, and Manuel Stoeckl. Adversarially Robust Coloring for Graph Streams. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 37:1-37:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ITCS.2022.37

Abstract

A streaming algorithm is considered to be adversarially robust if it provides correct outputs with high probability even when the stream updates are chosen by an adversary who may observe and react to the past outputs of the algorithm. We grow the burgeoning body of work on such algorithms in a new direction by studying robust algorithms for the problem of maintaining a valid vertex coloring of an n-vertex graph given as a stream of edges. Following standard practice, we focus on graphs with maximum degree at most Δ and aim for colorings using a small number f(Δ) of colors. 
A recent breakthrough (Assadi, Chen, and Khanna; SODA 2019) shows that in the standard, non-robust, streaming setting, (Δ+1)-colorings can be obtained while using only Õ(n) space. Here, we prove that an adversarially robust algorithm running under a similar space bound must spend almost Ω(Δ²) colors and that robust O(Δ)-coloring requires a linear amount of space, namely Ω(nΔ). We in fact obtain a more general lower bound, trading off the space usage against the number of colors used. From a complexity-theoretic standpoint, these lower bounds provide (i) the first significant separation between adversarially robust algorithms and ordinary randomized algorithms for a natural problem on insertion-only streams and (ii) the first significant separation between randomized and deterministic coloring algorithms for graph streams, since deterministic streaming algorithms are automatically robust.
We complement our lower bounds with a suite of positive results, giving adversarially robust coloring algorithms using sublinear space. In particular, we can maintain an O(Δ²)-coloring using Õ(n √Δ) space and an O(Δ³)-coloring using Õ(n) space.

Subject Classification

ACM Subject Classification
  • Theory of computation → Streaming, sublinear and near linear time algorithms
Keywords
  • Data streaming
  • graph algorithms
  • graph coloring
  • lower bounds
  • online algorithms

Metrics

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

Related Versions

References

  1. Amir Abboud, Keren Censor-Hillel, Seri Khoury, and Ami Paz. Smaller cuts, higher lower bounds. CoRR, abs/1901.01630, 2019. Google Scholar
  2. Kook Jin Ahn and Sudipto Guha. Graph sparsification in the semi-streaming model. In Automata, Languages and Programming, 36th Internatilonal Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part II, volume 5556 of Lecture Notes in Computer Science, pages 328-338. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-02930-1_27.
  3. 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. URL: https://doi.org/10.1137/1.9781611973099.40.
  4. Noga Alon and Sepehr Assadi. Palette sparsification beyond (Δ+1) vertex coloring. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020, August 17-19, 2020, Virtual Conference, volume 176 of LIPIcs, pages 6:1-6:22, 2020. URL: https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.6.
  5. Sepehr Assadi. Sublinear algorithms for (Delta + 1) vertex coloring. Lecture at Sublinear Algorithms and Nearest-Neighbor Search Workshop, Simons Institute; available online at https://www.youtube.com/watch?v=VU7Y_8ZcNu0&t=2206, 2018.
  6. Sepehr Assadi, Andrew Chen, and Glenn Sun. Deterministic graph coloring in the streaming model. arXiv preprint arXiv:2109.14891, 2021. Google Scholar
  7. 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. URL: https://doi.org/10.1137/1.9781611975482.48.
  8. Idan Attias, Edith Cohen, Moshe Shechner, and Uri Stemmer. A framework for adversarial streaming via differential privacy and difference estimators. CoRR, abs/2107.14527, 2021. URL: http://arxiv.org/abs/2107.14527.
  9. Omri Ben-Eliezer, Talya Eden, and Krzysztof Onak. Adversarially robust streaming via dense-sparse trade-offs. CoRR, abs/2109.03785, 2021. Google Scholar
  10. Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff, and Eylon Yogev. A framework for adversarially robust streaming algorithms. In Proc. 39th ACM Symposium on Principles of Database Systems, pages 63-80, 2020. URL: https://doi.org/10.1145/3375395.3387658.
  11. Omri Ben-Eliezer and Eylon Yogev. The adversarial robustness of sampling. In Proc. 39th ACM Symposium on Principles of Database Systems, pages 49-62. ACM, 2020. URL: https://doi.org/10.1145/3375395.3387643.
  12. Suman K. Bera, Amit Chakrabarti, and Prantar Ghosh. Graph coloring via degeneracy in streaming and other space-conscious models. In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 11:1-11:21, 2020. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.11.
  13. Suman Kalyan Bera and Prantar Ghosh. Coloring in graph streams. CoRR, abs/1807.07640, 2018. URL: http://arxiv.org/abs/1807.07640.
  14. Anup Bhattacharya, Arijit Bishnu, Gopinath Mishra, and Anannya Upasana. Even the easiest(?) graph coloring problem is not easy in streaming! In 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference, volume 185 of LIPIcs, pages 15:1-15:19, 2021. URL: https://doi.org/10.4230/LIPIcs.ITCS.2021.15.
  15. Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger, and Danupon Nanongkai. Dynamic algorithms for graph coloring. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1-20. SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975031.1.
  16. Sayan Bhattacharya, Fabrizio Grandoni, Janardhan Kulkarni, Quanquan C. Liu, and Shay Solomon. Fully dynamic (Δ+1)-coloring in constant update time. CoRR, abs/1910.02063, 2019. Google Scholar
  17. Vladimir Braverman, Avinatan Hassidim, Yossi Matias, Mariano Schain, Sandeep Silwal, and Samson Zhou. Adversarial robustness of streaming algorithms through importance sampling. CoRR, abs/2106.14952, 2021. URL: http://arxiv.org/abs/2106.14952.
  18. Amit Chakrabarti, Prantar Ghosh, and Manuel Stoeckl. Adversarially robust coloring for graph streams. CoRR, abs/2109.11130, 2021. URL: http://arxiv.org/abs/2106.14952.
  19. Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty, and David P. Woodruff. Pseudo-Deterministic Streaming. In Proc. 20th Conference on Innovations in Theoretical Computer Science, volume 151, pages 79:1-79:25, 2020. URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.79.
  20. Moritz Hardt and David P. Woodruff. How robust are linear sketches to adaptive inputs? In Proc. 45th Annual ACM Symposium on the Theory of Computing, pages 121-130, 2013. URL: https://doi.org/10.1145/2488608.2488624.
  21. Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer. Adversarially robust streaming algorithms via differential privacy. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. Google Scholar
  22. Monika Henzinger and Pan Peng. Constant-time dynamic (Δ+1)-coloring. In 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10-13, 2020, Montpellier, France, volume 154 of LIPIcs, pages 53:1-53:18, 2020. URL: https://doi.org/10.4230/LIPIcs.STACS.2020.53.
  23. Hossein Jowhari, Mert Saglam, and Gábor Tardos. Tight bounds for l_p samplers, finding duplicates in streams, and related problems. In Proc. 30th ACM Symposium on Principles of Database Systems, pages 49-58, 2011. URL: https://doi.org/10.1145/1989284.1989289.
  24. Haim Kaplan, Yishay Mansour, Kobbi Nissim, and Uri Stemmer. Separating adaptive streaming from oblivious streaming using the bounded storage model. In Advances in Cryptology - CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16-20, 2021, Proceedings, Part III, volume 12827 of Lecture Notes in Computer Science, pages 94-121. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-84252-9_4.
  25. Andrew McGregor. Graph stream algorithms: a survey. ACM SIGMOD Record, 43(1):9-20, 2014. URL: https://doi.org/10.1145/2627692.2627694.
  26. Ilya Mironov, Moni Naor, and Gil Segev. Sketching in adversarial environments. SIAM J. Comput., 40(6):1845-1870, 2011. URL: https://doi.org/10.1137/080733772.
  27. Noam Nisan. Pseudorandom generators for space-bounded computation. In Proc. 22nd Annual ACM Symposium on the Theory of Computing, pages 204-212, 1990. URL: https://doi.org/10.1007/BF01305237.
  28. Uri Stemmer. Separating adaptive streaming from oblivious streaming. Lecture at STOC 2021 Workshop: Robust Streaming, Sketching and Sampling, available online at https://www.youtube.com/watch?v=svgv-xw9DZc&t=7679s, 2021. Based on joint work with Haim Kaplan, Yishay Mansour, and Kobbi Nissim.
  29. David P. Woodruff and Samson Zhou. Tight bounds for adversarially robust streams and sliding windows via difference estimators. In Proc. 62nd Annual IEEE Symposium on Foundations of Computer Science, page to appear, 2021. 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