Document Open Access Logo

Relaxed Models for Adversarial Streaming: The Bounded Interruptions Model and the Advice Model

Authors Menachem Sadigurschi, Moshe Shechner, Uri Stemmer

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.91.pdf
  • Filesize: 0.75 MB
  • 14 pages

Document Identifiers

Author Details

Menachem Sadigurschi
  • Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva, Israel
Moshe Shechner
  • Blavatnik School of Computer Science, Tel Aviv University, Israel
Uri Stemmer
  • Blavatnik School of Computer Science, Tel Aviv University, Israel
  • Google Research, Tel Aviv, Israel

Funding

This project was partially supported by the Israel Science Foundation (grant 1871/19) and by Len Blavatnik and the Blavatnik Family foundation.

Cite AsGet BibTex

Menachem Sadigurschi, Moshe Shechner, and Uri Stemmer. Relaxed Models for Adversarial Streaming: The Bounded Interruptions Model and the Advice Model. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 91:1-91:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ESA.2023.91

Abstract

Streaming algorithms are typically analyzed in the oblivious setting, where we assume that the input stream is fixed in advance. Recently, there is a growing interest in designing adversarially robust streaming algorithms that must maintain utility even when the input stream is chosen adaptively and adversarially as the execution progresses. While several fascinating results are known for the adversarial setting, in general, it comes at a very high cost in terms of the required space. Motivated by this, in this work we set out to explore intermediate models that allow us to interpolate between the oblivious and the adversarial models. Specifically, we put forward the following two models: - The bounded interruptions model, in which we assume that the adversary is only partially adaptive. - The advice model, in which the streaming algorithm may occasionally ask for one bit of advice. We present both positive and negative results for each of these two models. In particular, we present generic reductions from each of these models to the oblivious model. This allows us to design robust algorithms with significantly improved space complexity compared to what is known in the plain adversarial model.

Subject Classification

ACM Subject Classification
  • Theory of computation → Streaming, sublinear and near linear time algorithms
Keywords
  • streaming
  • adversarial streaming

Metrics

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

Related Versions

References

  1. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Analyzing graph structure via linear measurements. In SODA, pages 459-467, 2012. URL: https://doi.org/10.1137/1.9781611973099.40.
  2. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Graph sketches: sparsification, spanners, and subgraphs. In PODS, pages 5-14, 2012. URL: https://doi.org/10.1145/2213556.2213560.
  3. Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. J. Comput. Syst. Sci., 58(1):137-147, 1999. URL: https://doi.org/10.1006/jcss.1997.1545.
  4. Idan Attias, Edith Cohen, Moshe Shechner, and Uri Stemmer. A framework for adversarial streaming via differential privacy and difference estimators. In ITCS, volume 251 of LIPIcs, pages 8:1-8:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. Google Scholar
  5. Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer. Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds. In STOC, pages 1671-1684. ACM, 2022. Google Scholar
  6. Omri Ben-Eliezer, Talya Eden, and Krzysztof Onak. Adversarially robust streaming via dense-sparse trade-offs. In SOSA@SODA, pages 214-227, 2022. Google Scholar
  7. Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff, and Eylon Yogev. A framework for adversarially robust streaming algorithms. J. ACM, 69(2):17:1-17:33, 2022. Google Scholar
  8. Omri Ben-Eliezer and Eylon Yogev. The adversarial robustness of sampling. In PODS, pages 49-62, 2020. Google Scholar
  9. Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Moshe Shechner, and Uri Stemmer. On the robustness of countsketch to adaptive inputs. In ICML, volume 162 of Proceedings of Machine Learning Research, pages 4112-4140. PMLR, 2022. Google Scholar
  10. Edith Cohen, Jelani Nelson, Tamas Sarlos, and Uri Stemmer. Tricking the hashing trick: A tight lower bound on the robustness of countsketch to adaptive inputs. Proceedings of the AAAI Conference on Artificial Intelligence, 37(6):7235-7243, 2023. Google Scholar
  11. Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In TCC, pages 265-284, 2006. Google Scholar
  12. A. C. Gilbert, B. Hemenway, A. Rudra, M. J. Strauss, and M. Wootters. Recovering simple signals. In Information Theory and Applications Workshop (ITA), pages 382-391, 2012. Google Scholar
  13. A. C. Gilbert, B. Hemenway, M. J. Strauss, D. P. Woodruff, and M. Wootters. Reusable low-error compressive sampling schemes through privacy. In IEEE Statistical Signal Processing Workshop (SSP), pages 536-539, 2012. Google Scholar
  14. Moritz Hardt and Jonathan Ullman. Preventing false discovery in interactive data analysis is hard. In FOCS. IEEE, october 19-21 2014. Google Scholar
  15. Moritz Hardt and David P. Woodruff. How robust are linear sketches to adaptive inputs? In STOC, pages 121-130, 2013. Google Scholar
  16. Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer. Adversarially robust streaming algorithms via differential privacy. J. ACM, 2022. URL: https://doi.org/10.1145/3556972.
  17. Hossein Jowhari, Mert Saglam, and Gábor Tardos. Tight bounds for lp samplers, finding duplicates in streams, and related problems. In PODS, pages 49-58. ACM, 2011. Google Scholar
  18. Hossein Jowhari, Mert Sağlam, and Gábor Tardos. Tight bounds for lp samplers, finding duplicates in streams, and related problems. In Proceedings of the thirtieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 49-58, 2011. Google Scholar
  19. Haim Kaplan, Yishay Mansour, Kobbi Nissim, and Uri Stemmer. Separating adaptive streaming from oblivious streaming using the bounded storage model. In CRYPTO, pages 94-121, 2021. Google Scholar
  20. 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.
  21. Menachem Sadigurschi, Moshe Shechner, and Uri Stemmer. Relaxed models for adversarial streaming: The bounded interruptions model and the advice model, 2023. URL: https://arxiv.org/abs/2301.09203.
  22. Thomas Steinke and Jonathan R. Ullman. Interactive fingerprinting codes and the hardness of preventing false discovery. In 2016 Information Theory and Applications Workshop, ITA 2016, La Jolla, CA, USA, January 31 - February 5, 2016, pages 1-41. IEEE, 2016. URL: https://doi.org/10.1109/ITA.2016.7888199.
  23. David P. Woodruff, Fred Zhang, and Samson Zhou. Streaming algorithms for learning with experts: Deterministic versus robust. CoRR, abs/2303.01709, 2023. URL: https://arxiv.org/abs/2303.01709.
  24. David P. Woodruff and Samson Zhou. Tight bounds for adversarially robust streams and sliding windows via difference estimators. In FOCS, pages 1183-1196, 2022. 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