2026-08-25T18:47:26Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:27249 2026-08-25T13:18:19Z ddc:004 open_access
On the Adversarial Robustness of Online Importance Sampling Kenneth-Mordoch, Yotam Sapir, Shay Importance sampling Adversarial robustness Streaming algorithms Coresets Cut sparsification Subspace embedding 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). Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik Yotam Kenneth-Mordoch and Shay Sapir 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.113 urn:nbn:de:0030-drops-272491 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.113 eng https://creativecommons.org/licenses/by/4.0/legalcode