4 papers
A Matrix Factorization Approach in Turnstile Streaming
Jan Bulanek, Ravi Kumar, Raghu Meka +2
We define the -point query problem in data streams. Given a fixed matrix , the goal is to maintain a vector under turnstile updates and answer each query with an esti…
Adaptively Robust Resettable Streaming
Edith Cohen, Elena Gribelyuk, Jelani Nelson +1
We study algorithms in the resettable streaming model, where the value of each key can either be increased or reset to zero. The model is suitable for applications such as active r…
Hot PATE: Private Aggregation of Distributions for Diverse Task
Edith Cohen, Benjamin Cohen-Wang, Xin Lyu +3
The Private Aggregation of Teacher Ensembles (PATE) framework enables privacy-preserving machine learning by aggregating responses from disjoint subsets of sensitive data. Adaptati…
One Attack to Rule Them All: Tight Quadratic Bounds for Adaptive Queries on Cardinality Sketches
Edith Cohen, Jelani Nelson, Tamás Sarlós +2
Cardinality sketches are compact data structures for representing sets or vectors. These sketches are space-efficient, typically requiring only logarithmic storage in the input siz…