SaTC: CORE: Small: Private Computation on Online Data

n today's world, we continuously generate sensitive data through various sources like financial transactions, smartphones, cameras, microphones, RFID readers, social media, and online shopping platforms, and performing various statistics on these collected data helps improve user experiences. However, this data often includes private information, and a key challenge is analyzing it without violating user privacy. The novelty of this project lies in uncovering the fundamental connections between performing statistical analysis on continuously generated data and various areas of mathematics. These insights are used to design fast and efficient algorithms. The project's broader significance and importance is prioritizing privacy for relatively simple tasks like statistical analysis as well as for more complex tasks, such as privately training machine learning models. Despite a growing interest in privacy-preserving continuous data analysis, existing algorithms for continual observation have seen limited large-scale implementation, with some notable exceptions. To understand this discrepancy, the project focuses on designing algorithms that guarantee a robust privacy guarantee known as differential privacy under a continual release model. By investigating the continual release of various statistics under the constraints of differential privacy, the project develops novel algorithms to gain deeper insights into the complexity-theoretic limitations of algorithms in the continual release model. The project first systematically explores the necessary steps to make differentially private continual observation more feasible and scalable by identifying key challenges for large-scale deployments with evolving datasets and developing new privacy-preserving algorithms tailored to these settings. The research advances foundational areas in mathematics and computer science, such as learning theory, statistical inference, operator algebras, probability theory, functional analysis, and streaming algorithms, contributing to the broader understanding of privacy-preserving continuous analysis. 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.