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

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

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.