Collaborative Research: AF: Medium: Sketching for privacy and privacy for sketching

数据集的草图只是一种压缩的表示，比存储原始数据消耗的内存要少得多，这允许回答一些查询集，并且可能还支持对数据库的更新。草图算法通常部署在低内存可用性的场景中，如传感器网络，低延迟应用程序，其中低内存解决方案适合缓存，因此速度更快，大数据应用程序作为算法加速的工具，如大规模机器学习，或分布式应用程序，其中压缩草图可以在服务器之间传输，比（大型）原始数据更便宜。最近的一些行业和政府应用需要这样的算法，在各种设置中额外维护用户隐私，同时在内存、运行时和/或通信方面也很有效，这可以通过草图来完成。该项目旨在推进特定应用的素描算法发展的艺术状态。这尤其包括减少具有隐私要求的分布式环境中的通信，以及进一步将隐私开发为一种算法工具，以设计新的随机素描算法，即使在具有自适应对手的环境中也能提供正确性保证。此外，该项目旨在进一步发展素描的使用，为统计学习问题提供低内存解决方案。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

A sketch of a dataset is simply a compressed representation, consuming much less memory than what it would take to store the raw data, which allows for answering some set of queries and possibly also supporting updates to the database. Sketching algorithms are typically deployed in scenarios with low memory availability such as in sensor networks, low-latency applications where low memory solutions fit in cache and are thus faster, big data applications as a tool for algorithmic speed-up such as large-scale machine learning, or distributed applications in which compressed sketches can be transmitted between servers more cheaply than the (large) raw data. Several recent industry and government applications have necessitated such algorithms that additionally maintain user privacy in a variety of settings, while also being efficient in terms of memory, runtime, and/or communication, which can be accomplished via sketching.This project aims to advance the state of the art in the development of sketching algorithms for particular applications. This in particular includes reducing communication in distributed environments with privacy requirements, as well as further developing privacy as an algorithmic tool to design new randomized sketching algorithms that provide correctness guarantees even in environments with adaptive adversaries. In addition, the project aims to further develop the use of sketching to provide low-memory solutions to statistical learning problems.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.