Pan-private Algorithms: When Memory Does Not Help

Darakhshan Mir, S. Muthukrishnan, Aleksandar Nikolov +1

Consider updates arriving online in which the $t$th input is $(i_t,d_t)$, where $i_t$'s are thought of as IDs of users. Informally, a randomized function $f$ is {\em differentially…