Jarosław Błasiok

collaborators

3 papers

cs.DS2018

Towards Instance-Optimal Private Query Release

Jaroslaw Blasiok, Mark Bun, Aleksandar Nikolov +1

We study efficient mechanisms for the query release problem in differential privacy: given a workload of $m$ statistical queries, output approximate answers to the queries while sa…

cs.DS2018

Optimal streaming and tracking distinct elements with high probability

Jarosław Błasiok

The distinct elements problem is one of the fundamental problems in streaming algorithms --- given a stream of integers in the range ${1, \dots, n}$ , we wish to provide a $(1+\var…

cs.LG2016

An improved analysis of the ER-SpUD dictionary learning algorithm

Jarosław Błasiok, Jelani Nelson

In "dictionary learning" we observe $Y = A X + E$ for some $Y \in R^{n \times p}$ , $A \in R^{m \times n}$ , and $X \in R^{m \times p}$ . The matrix $Y$ is observed,…