The Sample Complexity of Distribution-Free Parity Learning in the Robust Shuffle Model
Not on the map. Why?
Abstract (arXiv)
We provide a lowerbound on the sample complexity of distribution-free parity learning in the realizable case in the shuffle model of differential privacy. Namely, we show that the sample complexity of learning d-bit parity functions is Omega(2d/2). Our result extends a recent similar lowerbound on the sample complexity of private agnostic learning of parity functions in the shuffle model by Cheu and Ullman. We also sketch a simple shuffle model protocol demonstrating that our results are tight up to poly(d) factors.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 12 of its 26 references that are in the map. First posted on arXiv 29 Mar 2021.
Builds on
12 of 26 references.
References · 12
- 2018Amplification by Shuffling: From Local to Central Differential Privacy via Anonymitycited by 163
- 2018Distributed Differential Privacy via Shufflingcited by 115
- 2019The Privacy Blanket of the Shuffle Modelcited by 73
- 2017Prochlo: Strong Privacy for Analytics in the Crowdcited by 51
- 2020Private Summation in the Multi-Message Shuffle Modelcited by 34
- 2019Scalable and Differentially Private Distributed Aggregation in the Shuffled Modelcited by 20
- 2019Separating Local & Shuffled Differential Privacy via Histogramscited by 16
- 2019Private Aggregation from Fewer Anonymous Messagescited by 15
- 2020Connecting Robust Shuffle Privacy and Pan-Privacycited by 12
- 2019Differentially Private Summation with Multi-Message Shufflingcited by 9
- 2020On Distributed Differential Privacy and Counting Distinct Elementscited by 8
- 2020The Limits of Pan Privacy and Shuffle Privacy for Learning and Estimationcited by 7
Built on by
Citing papers per year: 2026: 1.
1 paper.