| Title: |
Uniformity Testing Under User-Level Local Privacy |
| Authors: |
Canonne, Clément L.; Gentle, Abigail; Singhal, Vikrant |
| Contributors: |
Clément L. Canonne and Abigail Gentle and Vikrant Singhal |
| Publisher Information: |
Schloss Dagstuhl – Leibniz-Zentrum für Informatik |
| Publication Year: |
2026 |
| Collection: |
DROPS - Dagstuhl Research Online Publication Server (Schloss Dagstuhl - Leibniz Center for Informatics ) |
| Subject Terms: |
Differential Privacy; Local Differential Privacy; Uniformity Testing; Identity Testing; Hypothesis Testing; User-Level Differential Privacy; Person-Level Differential Privacy |
| Description: |
We initiate the study of distribution testing under user-level local differential privacy, where each of n users contributes m samples from the unknown underlying distribution. This setting, albeit very natural, is significantly more challenging than the usual locally private setting, as for the same parameter ε the privacy guarantee must now apply to a full batch of m data points. While some recent work considers distribution learning in this user-level setting, nothing was known for even the most fundamental testing task, uniformity testing (and its generalization, identity testing). We address this gap, by providing (nearly) sample-optimal user-level LDP algorithms for uniformity and identity testing. Motivated by practical considerations, our main focus is on the private-coin, symmetric setting, which does not require users to share a common random seed nor to have been assigned a globally unique identifier. |
| Document Type: |
article in journal/newspaper; conference object |
| File Description: |
application/pdf |
| Language: |
English |
| Relation: |
Is Part Of LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026); https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.33 |
| DOI: |
10.4230/LIPIcs.ITCS.2026.33 |
| Availability: |
https://doi.org/10.4230/LIPIcs.ITCS.2026.33; https://nbn-resolving.org/urn:nbn:de:0030-drops-253201; https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.33 |
| Rights: |
https://creativecommons.org/licenses/by/4.0/legalcode |
| Accession Number: |
edsbas.1E0C9A95 |
| Database: |
BASE |