DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2023.91

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

Authors: Menachem Sadigurschi, Moshe Shechner, and Uri Stemmer

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{sadigurschi_et_al:LIPIcs.ESA.2023.91,
  author =	{Sadigurschi, Menachem and Shechner, Moshe and Stemmer, Uri},
  title =	{{Relaxed Models for Adversarial Streaming: The Bounded Interruptions Model and the Advice Model}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{91:1--91:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.91},
  URN =		{urn:nbn:de:0030-drops-187445},
  doi =		{10.4230/LIPIcs.ESA.2023.91},
  annote =	{Keywords: streaming, adversarial streaming}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2023.8

A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators

Authors: Idan Attias, Edith Cohen, Moshe Shechner, and Uri Stemmer

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract

Classical streaming algorithms operate under the (not always reasonable) assumption that the input stream is fixed in advance. Recently, there is a growing interest in designing robust streaming algorithms that provide provable guarantees even when the input stream is chosen adaptively as the execution progresses. We propose a new framework for robust streaming that combines techniques from two recently suggested frameworks by Hassidim et al. [NeurIPS 2020] and by Woodruff and Zhou [FOCS 2021]. These recently suggested frameworks rely on very different ideas, each with its own strengths and weaknesses. We combine these two frameworks into a single hybrid framework that obtains the "best of both worlds", thereby solving a question left open by Woodruff and Zhou.

Cite as

Idan Attias, Edith Cohen, Moshe Shechner, and Uri Stemmer. A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{attias_et_al:LIPIcs.ITCS.2023.8,
  author =	{Attias, Idan and Cohen, Edith and Shechner, Moshe and Stemmer, Uri},
  title =	{{A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{8:1--8:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.8},
  URN =		{urn:nbn:de:0030-drops-175115},
  doi =		{10.4230/LIPIcs.ITCS.2023.8},
  annote =	{Keywords: Streaming, adversarial robustness, differential privacy}
}

Search Results

Documents authored by Shechner, Moshe

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

Abstract

Cite as

A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators

Abstract

Cite as

Thanks for your feedback!

Could not send message