# The Sample Complexity of Distribution-Free Parity Learning in the Robust Shuffle Model

arXiv: https://arxiv.org/abs/2103.15690 · HTML: https://mlsanity.com/paper/2103.15690/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 26 references that are in the map.
- First posted on arXiv 29 Mar 2021.

## Builds on (most cited first, 12 of 12)

- [Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity](https://mlsanity.com/paper/1811.12469/) (2018)
- [Distributed Differential Privacy via Shuffling](https://mlsanity.com/paper/1808.01394/) (2018)
- [The Privacy Blanket of the Shuffle Model](https://mlsanity.com/paper/1903.02837/) (2019)
- [Prochlo: Strong Privacy for Analytics in the Crowd](https://mlsanity.com/paper/1710.00901/) (2017)
- [Private Summation in the Multi-Message Shuffle Model](https://mlsanity.com/paper/2002.00817/) (2020)
- [Scalable and Differentially Private Distributed Aggregation in the Shuffled Model](https://mlsanity.com/paper/1906.08320/) (2019)
- [Separating Local & Shuffled Differential Privacy via Histograms](https://mlsanity.com/paper/1911.06879/) (2019)
- [Private Aggregation from Fewer Anonymous Messages](https://mlsanity.com/paper/1909.11073/) (2019)
- [Connecting Robust Shuffle Privacy and Pan-Privacy](https://mlsanity.com/paper/2004.09481/) (2020)
- [Differentially Private Summation with Multi-Message Shuffling](https://mlsanity.com/paper/1906.09116/) (2019)
- [On Distributed Differential Privacy and Counting Distinct Elements](https://mlsanity.com/paper/2009.09604/) (2020)
- [The Limits of Pan Privacy and Shuffle Privacy for Learning and Estimation](https://mlsanity.com/paper/2009.08000/) (2020)

## Built on by (most cited first, 1 of 1)

- [On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCA](https://mlsanity.com/paper/2606.21951/) (2026)

## 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.