DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.113

On the Adversarial Robustness of Online Importance Sampling

Authors: Yotam Kenneth-Mordoch and Shay Sapir

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract

Online sampling algorithms, which irrevocably either keep or discard each stream element, have seen wide use in streaming due to their efficiency and simplicity. Braverman et al. [NeurIPS 2021] claimed that online importance-sampling algorithms, where elements are sampled proportionally to some notion of importance, succeed with high probability when their input stream is adaptively chosen by an adversary. Unfortunately, their results on importance sampling do not beat trivial bounds in many instances. Therefore, we reopen the question about the robustness of online importance sampling to adaptive inputs. This question was also addressed by Jiang, Peng and Weinstein [FOCS 2023] for the problem of 𝓁₂-subspace embedding. We develop a unified framework for online importance sampling algorithms in adaptive streams. This framework offers two main advantages: first, it provides better bounds than prior work, and second, it unifies and simplifies the analysis of importance sampling algorithms across different problems. We then leverage the framework to provide algorithms for cut sparsification in hypergraphs and 𝓁_p-subspace embeddings in adaptive streams whose space complexity nearly matches the oblivious case (non-adaptive).

Cite as

Yotam Kenneth-Mordoch and Shay Sapir. On the Adversarial Robustness of Online Importance Sampling. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 113:1-113:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kennethmordoch_et_al:LIPIcs.ESA.2026.113,
  author =	{Kenneth-Mordoch, Yotam and Sapir, Shay},
  title =	{{On the Adversarial Robustness of Online Importance Sampling}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{113:1--113:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.113},
  URN =		{urn:nbn:de:0030-drops-272491},
  doi =		{10.4230/LIPIcs.ESA.2026.113},
  annote =	{Keywords: Importance sampling, Adversarial robustness, Streaming algorithms, Coresets, Cut sparsification, Subspace embedding}
}

Document

DOI: 10.4230/LIPIcs.ESA.2025.100

Cut-Query Algorithms with Few Rounds

Authors: Yotam Kenneth-Mordoch and Robert Krauthgamer

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract

In the cut-query model, the algorithm can access the input graph G = (V,E) only via cut queries that report, given a set S ⊆ V, the total weight of edges crossing the cut between S and V⧵ S. This model was introduced by Rubinstein, Schramm and Weinberg [ITCS'18] and its investigation has so far focused on the number of queries needed to solve optimization problems, such as global minimum cut. We turn attention to the round complexity of cut-query algorithms, and show that several classical problems can be solved in this model with only a constant number of rounds. Our main results are algorithms for finding a minimum cut in a graph, that offer different tradeoffs between round complexity and query complexity, where n = |V| and δ(G) denotes the minimum degree of G: (i) Õ(n^{4/3}) cut queries in two rounds in unweighted graphs; (ii) Õ(rn^{1+1/r}/δ(G)^{1/r}) queries in 2r+1 rounds for any integer r ≥ 1 again in unweighted graphs; and (iii) Õ(rn^{1+(1+log_n W)/r}) queries in 4r+3 rounds for any r ≥ 1 in weighted graphs. We also provide algorithms that find a minimum (s,t)-cut and approximate the maximum cut in a few rounds.

Cite as

Yotam Kenneth-Mordoch and Robert Krauthgamer. Cut-Query Algorithms with Few Rounds. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 100:1-100:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kennethmordoch_et_al:LIPIcs.ESA.2025.100,
  author =	{Kenneth-Mordoch, Yotam and Krauthgamer, Robert},
  title =	{{Cut-Query Algorithms with Few Rounds}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{100:1--100:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.100},
  URN =		{urn:nbn:de:0030-drops-245692},
  doi =		{10.4230/LIPIcs.ESA.2025.100},
  annote =	{Keywords: Cut Queries, Round Complexity, Submodular Optimization}
}

Search Results

Documents authored by Kenneth-Mordoch, Yotam

On the Adversarial Robustness of Online Importance Sampling

Abstract

Cite as

Cut-Query Algorithms with Few Rounds

Abstract

Cite as

Thanks for your feedback!

Could not send message