Algorithms and Theory

Common datasets have the form of elements with keys (e.g., transactions and products) and the goal is to perform analytics on the aggregated form of key and frequency pairs. A weighted sample of keys by (a function of) frequency is a highly versatile summary that provides a sparse set of representative keys and supports approximate evaluations of query statistics. We propose private weighted...

Streaming algorithms are algorithms for processing large data streams, using only a limited amount of memory. Classical streaming algorithms typically work under the assumption that the input stream is chosen independently from the internal state of the algorithm. Algorithms that utilize this assumption are called oblivious algorithms. Recently, there is a growing interest in studying streaming...

Motivated by modern applications, such as online advertisement and recommender systems, we study the top-$k$ \xtm contextual bandits problem, where the total number of arms can be enormous, and the learner is allowed to select $k$ arms and observe all or some of the rewards for the chosen arms. We first propose an algorithm for the non-\xtm realizable setting, utilizing the Inverse Gap...

We study k-means clustering in the non-interactive (aka one-round) local model of differential privacy. We give an approximation algorithm that requires a single round of communication and achieves an approximation ratio arbitrarily close to the best non private approximation algorithm. To show the flexibility of our framework, we also demonstrate that it yields a similar near-optimal...