53 citations · 57 across the 3 of their papers we have counts for
Showing cs.DSShow all
2 papers · 1 filter
cs.DS2014
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…
cs.DS2013
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…