73 citations · 585 across the 58 of their papers we have counts for
4 papers · 1 filter
Skyline Identification in Multi-Armed Bandits
Albert Cheu, Ravi Sundaram, Jonathan Ullman
We introduce a variant of the classical PAC multi-armed bandit problem. There is an ordered set of arms , each with some stochastic reward drawn from some unkn…
Tight Lower Bounds for Differentially Private Selection
Thomas Steinke, Jonathan Ullman
A pervasive task in the differential privacy literature is to select the items of "highest quality" out of a set of items, where the quality of each item depends on a sensi…
The Price of Selection in Differential Privacy
Mitali Bafna, Jonathan Ullman
In the differentially private top- selection problem, we are given a dataset , in which each row belongs to an individual and each column correspon…
Subgaussian Tail Bounds via Stability Arguments
Thomas Steinke, Jonathan Ullman
Sums of independent, bounded random variables concentrate around their expectation approximately as well a Gaussian of the same variance. Well known results of this form include th…