73 citations · 585 across the 58 of their papers we have counts for
6 papers · 1 filter
Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery
Thomas Steinke, Jonathan Ullman
We show an essentially tight bound on the number of adaptively chosen statistical queries that a computationally efficient algorithm can answer accurately given samples from an…
Preventing False Discovery in Interactive Data Analysis is Hard
Moritz Hardt, Jonathan Ullman
We show that, under a standard hardness assumption, there is no computationally efficient algorithm that given samples from an unknown distribution can give valid answers to $n…
Space Lower Bounds for Itemset Frequency Sketches
Edo Liberty, Michael Mitzenmacher, Justin Thaler +1
Given a database, computing the fraction of rows that contain a query itemset or determining whether this fraction is above some threshold are fundamental operations in data mining…
Private Multiplicative Weights Beyond Linear Queries
Jonathan Ullman
A wide variety of fundamental data analyses in machine learning, such as linear and logistic regression, require minimizing a convex function defined by the data. Since the data ma…
Privately Solving Linear Programs
Justin Hsu, Aaron Roth, Tim Roughgarden +1
In this paper, we initiate the systematic study of solving linear programs under differential privacy. The first step is simply to define the problem: to this end, we introduce sev…
An Anti-Folk Theorem for Large Repeated Games with Imperfect Monitoring
Mallesh M. Pai, Aaron Roth, Jonathan Ullman
We study infinitely repeated games in settings of imperfect monitoring. We first prove a family of theorems that show that when the signals observed by the players satisfy a condit…