Differentially Private Set Representations
Sarvar Patel *, Giuseppe Persiano *, Joon Young Seo *, Kevin Yeo * · 2025
Read Differentially Private Set Representations by Sarvar Patel *, Giuseppe Persiano *, Joon Young Seo *, Kevin Yeo * (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-16680.txt.
Description
Sarvar Patel, Giuseppe Persiano, Joon Young Seo, and Kevin Yeo studied private ways to represent sets in 2025. The problem is to store a small set drawn from a huge universe while hiding whether any one item is present. Such privacy is called differential privacy.
Their first method builds a private form with low error and compact space, and it decodes fast. A second method gives a stronger form of privacy with like space but slow decoding. The authors also prove lower bounds that match their methods up to small factors. Their trick is to embed sets into random linear systems, a shift from older work that added noise to a plain answer.
Catalog record
| CREATOR | Sarvar Patel *, Giuseppe Persiano *, Joon Young Seo *, Kevin Yeo * |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-16680