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

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

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.