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

数据集的草图只是一个压缩的表示，比存储原始数据消耗的内存少得多，这允许回答一些查询集，也可能支持对数据库的更新。草绘算法通常部署在低内存可用性的场景中，例如传感器网络，低内存解决方案适合高速缓存的低延迟应用，因此速度更快，大数据应用作为算法加速的工具，例如大规模机器学习，或分布式应用，其中压缩草图可以在服务器之间传输比（大）原始数据更便宜。最近的几个行业和政府的应用程序有必要这样的算法，另外保持用户的隐私在各种设置，同时也是有效的内存，运行时，和/或通信，这可以通过sketching.This项目的目的是推进国家的艺术在特定应用程序的草图算法的发展。这特别包括减少具有隐私要求的分布式环境中的通信，以及进一步开发隐私作为算法工具，以设计新的随机草图算法，即使在具有自适应对手的环境中也能提供正确性保证。此外，该项目旨在进一步发展草图的使用，为统计学习问题提供低记忆解决方案。该奖项反映了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.