Poster
Differentially Private Set Representations
Sarvar Patel · Giuseppe Persiano · Joon Young Seo · Kevin Yeo
West Ballroom A-D #6209
Abstract:
We study the problem of differentially private (DP) mechanisms for representingsets of size from a large universe.Our first construction creates-DP representations with error probability of using space at most bits wherethe time to construct a representation is while decoding time is .We also present a second algorithm for pure -DP representations with the same error using space at most bits, but requiring large decoding times.Our algorithms match the lower bounds on privacy-utility trade-offs (including constants but ignoring factors) and we also present a new space lower boundmatching our constructions up to small constant factors.To obtain our results, we design a new approach embedding sets into random linear systemsdeviating from most prior approaches that inject noise into non-private solutions.
Chat is not available.