Collaborative Research: AF: Small: Resilient Data Stream Algorithms

Massive amounts of data are collected or generated in industries such as finance and healthcare; in scientific fields such as genomics and high-energy physics; and in technological applications such as cloud computing and training machine learning models. This has motivated the design and analysis of data stream algorithms, a highly productive research area within computer science. The focus is typically on algorithms with provable guarantees regarding their running time, memory usage, and accuracy. However, the guarantees established in previous work often require explicit and implicit assumptions about how the algorithms will be applied. Many existing algorithms become ineffective when these assumptions do not hold. This project aims to design resilient data stream algorithms that are less dependent on such assumptions and more reliable in practice. It will also support curriculum development and the training of graduate students. The project tackles several key challenges in the theory of data stream algorithms. First, it aims to develop adversarially robust algorithms that remain effective even when inputs are adaptively chosen in response to algorithmic behavior. This situation naturally arises in interactive data analysis. Second, the project investigates parameter-free and non-adaptive algorithms that do not rely on prior knowledge of problem-specific parameters, avoiding the costly, generic technique of multiple instantiations. Third, it examines when the performance of randomized streaming methods can be matched or approximated by pseudo-deterministic or deterministic algorithms. Such algorithms provide reproducibility, which is important in experimental science. Finally, the project seeks data stream algorithms that address fault-tolerance, ensuring correctness amid hardware or communication errors. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.