53 citations · 57 across the 3 of their papers we have counts for
4 papers
Sample Complexity Bounds on Differentially Private Learning via Communication Complexity
Vitaly Feldman, David Xiao
In this work we analyze the sample complexity of classification by differentially private algorithms. Differential privacy is a strong and well-studied notion of privacy introduced…
Redrawing the Boundaries on Purchasing Data from Privacy-Sensitive Individuals
Kobbi Nissim, Salil Vadhan, David Xiao
We prove new positive and negative results concerning the existence of truthful and individually rational mechanisms for purchasing private data from individuals with unbounded and…
Improved bounds for the randomized decision tree complexity of recursive majority
Frederic Magniez, Ashwin Nayak, Miklos Santha +3
We consider the randomized decision tree complexity of the recursive 3-majority function. We prove a lower bound of for the two-sided-error randomized dec…
Lower bounds on information complexity via zero-communication protocols and applications
Iordanis Kerenidis, Sophie Laplante, Virginie Lerays +2
We show that almost all known lower bound methods for communication complexity are also lower bounds for the information complexity. In particular, we define a relaxed version of t…