Necessity of Block Designs for Optimal Locally Private Distribution Estimation
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918116627316736 |
|---|---|
| author | Gentle, Abigail |
| author_facet | Gentle, Abigail |
| contents | Local differential privacy represents the gold standard for preserving the privacy of data before it leaves the device, and distribution estimation under this model has been well studied. Recently, protocols built upon balanced incomplete block designs were shown to achieve optimal error for this problem. However, it remained unknown whether other constructions could also be optimal. We resolve this question by proving that any protocol achieving optimal error must correspond to some balanced incomplete block design. This result, combined with prior work, completely characterises the set of optimal protocols for this problem. As a consequence, the protocols that achieve optimal error and optimal communication are only those based on symmetrical balanced incomplete block designs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_05110 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Necessity of Block Designs for Optimal Locally Private Distribution Estimation Gentle, Abigail Information Theory Cryptography and Security Data Structures and Algorithms Local differential privacy represents the gold standard for preserving the privacy of data before it leaves the device, and distribution estimation under this model has been well studied. Recently, protocols built upon balanced incomplete block designs were shown to achieve optimal error for this problem. However, it remained unknown whether other constructions could also be optimal. We resolve this question by proving that any protocol achieving optimal error must correspond to some balanced incomplete block design. This result, combined with prior work, completely characterises the set of optimal protocols for this problem. As a consequence, the protocols that achieve optimal error and optimal communication are only those based on symmetrical balanced incomplete block designs. |
| title | Necessity of Block Designs for Optimal Locally Private Distribution Estimation |
| topic | Information Theory Cryptography and Security Data Structures and Algorithms |
| url | https://arxiv.org/abs/2508.05110 |