4 Search Results for "Sadigurschi, Menachem"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.40
A Simple and Robust Protocol for Distributed Counting

Authors: Edith Cohen, Moshe Shechner, and Uri Stemmer

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We revisit the distributed counting problem, where a server must continuously approximate the total number of events occurring across k sites while minimizing communication. The communication complexity of this problem is known to be Θ(k/(ε)log N) for deterministic protocols. Huang, Yi, and Zhang (2012) showed that randomization can reduce this to Θ((√k)/ε log N), but their analysis is restricted to the oblivious setting, where the stream of events is independent of the protocol’s outputs. Xiong, Zhu, and Huang (2023) presented a robust protocol for distributed counting that removes the oblivious assumption. However, their communication complexity is suboptimal by a polylog(k) factor and their protocol is substantially more complex than the oblivious protocol of Huang et al. (2012). This left open a natural question: could it be that the simple protocol of Huang et al. (2012) is already robust? We resolve this question with two main contributions. First, we show that the protocol of Huang et al. (2012) is itself not robust by constructing an explicit adaptive attack that forces it to lose its accuracy. Second, we present a new, surprisingly simple, robust protocol for distributed counting that achieves the optimal communication complexity of O((√k)/ε log N). Our protocol is simpler than that of Xiong et al. (2023), perhaps even simpler than that of Huang et al. (2012), and is the first to match the optimal oblivious complexity in the adaptive setting.
Cite as

Edith Cohen, Moshe Shechner, and Uri Stemmer. A Simple and Robust Protocol for Distributed Counting. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 40:1-40:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.ITCS.2026.40,
  author =	{Cohen, Edith and Shechner, Moshe and Stemmer, Uri},
  title =	{{A Simple and Robust Protocol for Distributed Counting}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{40:1--40:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.40},
  URN =		{urn:nbn:de:0030-drops-253272},
  doi =		{10.4230/LIPIcs.ITCS.2026.40},
  annote =	{Keywords: Distributed Streaming, Adversarial Streaming}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.16
Robust Streaming Against Low-Memory Adversaries

Authors: Omri Ben-Eliezer, Krzysztof Onak, and Sandeep Silwal

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
Robust streaming, the study of streaming algorithms that provably work when the stream is generated by an adaptive adversary, has seen tremendous progress in recent years. However, fundamental barriers remain: the best known algorithm for turnstile F_p-estimation in the robust streaming setting is exponentially worse than in the oblivious setting, and closing this gap seems difficult. Arguably, one possible cause of this barrier is the adversarial model, which may be too strong: unlike the space-bounded streaming algorithm, the adversary can memorize the entire history of the interaction with the algorithm. Can we then close the exponential gap if we insist that the adversary itself is an adaptive but low-memory entity, roughly as powerful as (or even weaker than) the algorithm? In this work we present the first set of models and results aimed towards this question. We design efficient robust streaming algorithms against adversaries that are fully adaptive but have no long-term memory ("memoryless") or very little memory of the history of interaction. Roughly speaking, a memoryless adversary only sees, at any given round, the last output of the algorithm (and does not even know the current time) and can generate an unlimited number of independent coin tosses. A low-memory adversary is similar, but maintains an additional small buffer. While these adversaries may seem quite limited at first glance, we show that this adversarial model is strong enough to produce streams that have high flip number and density in the context of F₂-estimation, which rules out most known robustification techniques. We then design a new simple approach, similar to the computation paths framework, to obtain efficient algorithms against memoryless and low-memory adversaries for a wide class of order-invariant problems. We conclude by posing various open questions proposing further exploration of the landscape of robust streaming against fully adaptive but computationally constrained adversaries.
Cite as

Omri Ben-Eliezer, Krzysztof Onak, and Sandeep Silwal. Robust Streaming Against Low-Memory Adversaries. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 16:1-16:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{beneliezer_et_al:LIPIcs.ITCS.2026.16,
  author =	{Ben-Eliezer, Omri and Onak, Krzysztof and Silwal, Sandeep},
  title =	{{Robust Streaming Against Low-Memory Adversaries}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{16:1--16:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.16},
  URN =		{urn:nbn:de:0030-drops-253037},
  doi =		{10.4230/LIPIcs.ITCS.2026.16},
  annote =	{Keywords: robust streaming, adaptive robustness, bounded-space adversaries}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.6
Facility Location in the Sublinear Geometric Model

Authors: Morteza Monemizadeh

Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)

Abstract
In the sublinear geometric model, we are provided with an oracle access to a point set P of n points in a bounded discrete space [Δ]², where Δ = n^O(1) is a polynomially bounded number in n. That is, we do not have direct access to the points, but we can make certain types of queries and there is an oracle that responds to our queries. The type of queries that we assume we can make in this paper, are range counting queries where ranges are axis-aligned rectangles (that are basic primitives in database [Srikanta Tirthapura and David P. Woodruff, 2012; Bentley, 1975; Mark de Berg et al., 2008], computational geometry [Pankaj K. Agarwal, 2004; Pankaj K. Agarwal et al., 1996; Boris Aronov et al., 2010; Boris Aronov et al., 2009], and machine learning [Menachem Sadigurschi and Uri Stemmer, 2021; Long and Tan, 1998; Michael J. Kearns and Umesh V. Vazirani, 1995; Michael J. Kearns and Umesh V. Vazirani, 1994]). The oracle then answers these queries by returning the number of points that are in queried ranges. Let {Alg} be an algorithm that (exactly or approximately) solves a problem 𝒫 in the sublinear geometric model. The query complexity of Alg is measured in terms of the number of queries that Alg makes to solve 𝒫. In this paper, we study the complexity of the (uniform) Euclidean facility location problem in the sublinear geometric model. We develop a randomized sublinear algorithm that with high probability, (1+ε)-approximates the cost of the Euclidean facility location problem of the point set P in the sublinear geometric model using Õ(√n) range counting queries. We complement this result by showing that approximating the cost of the Euclidean facility location problem within o(log(n))-factor in the sublinear geometric model using the sampling strategy that we propose for our sublinear algorithm needs Ω̃(n^{1/4}) RangeCount queries. We leave it as an open problem whether such a polynomial lower bound on the number of RangeCount queries exists for any randomized sublinear algorithm that approximates the cost of the facility location problem within a constant factor.
Cite as

Morteza Monemizadeh. Facility Location in the Sublinear Geometric Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 6:1-6:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{monemizadeh:LIPIcs.APPROX/RANDOM.2023.6,
  author =	{Monemizadeh, Morteza},
  title =	{{Facility Location in the Sublinear Geometric Model}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{6:1--6:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.6},
  URN =		{urn:nbn:de:0030-drops-188315},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.6},
  annote =	{Keywords: Facility Location, Sublinear Geometric Model, Range Counting Queries}
}
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}
}
  • Refine by Type
  • 4 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2026
  • 2 2023

  • Refine by Author
  • 2 Shechner, Moshe
  • 2 Stemmer, Uri
  • 1 Ben-Eliezer, Omri
  • 1 Cohen, Edith
  • 1 Monemizadeh, Morteza
  • Show More...

  • Refine by Series/Journal
  • 4 LIPIcs

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

  • Refine by Keyword
  • 1 Adversarial Streaming
  • 1 Distributed Streaming
  • 1 Facility Location
  • 1 Range Counting Queries
  • 1 Sublinear Geometric Model
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact