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

CREATORSarvar Patel *, Giuseppe Persiano *, Joon Young Seo *, Kevin Yeo *
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE41 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-16680

Browse the full library · About the Tower of Babel