Finding missing items requires strong forms of randomness

DOI10.4230/LIPICS.CCC.2024.28MaRDI QIDQ6866465zbMATH OpenFDO

Authors Amit Chakrabarti

Publication date 28 January 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.CCC.2024.28

zbMATH Keywords

samplingsketchinglower boundsderandomizationspace complexitydata streamingadversarial robustness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites work

• scientific article; zbMATH DE number 7829269 (Why is no real title available?)
• scientific article; zbMATH DE number 7829339 (Why is no real title available?)
• Adversarially robust streaming via dense-sparse trade-offs
• Finding missing items requires strong forms of randomness
• How robust are linear sketches to adaptive inputs?
• Mirror games against an open book player
• On read-once vs. multiple access to randomness in logspace
• Private vs. common random bits in communication complexity
• Pseudo-Deterministic Streaming.
• Separating adaptive streaming from oblivious streaming using the bounded storage model
• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• Streaming algorithms for the missing item finding problem
• The space complexity of mirror games
• Tight bounds for adversarially robust streams and sliding windows via difference estimators
• Towards Optimal Moment Estimation in Streaming and Distributed Models

Cited in

(1)

• Finding missing items requires strong forms of randomness

This page was built for publication: Finding missing items requires strong forms of randomness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6866465)