1 Search Results for "Attias, Idan"

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-dev.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}
}
  • Refine by Author
  • 1 Attias, Idan
  • 1 Cohen, Edith
  • 1 Shechner, Moshe
  • 1 Stemmer, Uri

  • Refine by Classification
  • 1 Theory of computation → Streaming, sublinear and near linear time algorithms

  • Refine by Keyword
  • 1 Streaming
  • 1 adversarial robustness
  • 1 differential privacy

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2023

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