A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators

Streaming algorithms are algorithms for processing large data streams while using only a limited amount of memory, significantly smaller than what is needed to store the entire data stream. Data streams occur in many applications including computer networking, databases, and natural language processing. The seminal work of Alon, Matias, and Szegedy[AMS99] initiated an extensive theoretical study and further applications of streaming algorithms. In this work we focus on streaming algorithms that aim to maintain, at any point in time, an approximation for the value of some (predefined) real-valued function of the input stream. Such streaming algorithms are sometimes referred to as strong trackers. For example, this predefined function might count the number of distinct elements in the stream.