# A Unified Characterization of Private Learnability via Graph Theory

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 33 references that are in the map.
- First posted on arXiv 8 Apr 2023.

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

- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Private PAC learning implies finite Littlestone dimension](https://mlsanity.com/paper/1806.00949/) (2018)
- [An Equivalence Between Private Classification and Online Prediction](https://mlsanity.com/paper/2003.00563/) (2020)
- [Reproducibility in Learning](https://mlsanity.com/paper/2201.08430/) (2022)
- [Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization](https://mlsanity.com/paper/2303.12921/) (2023)
- [Sample Complexity Bounds on Differentially Private Learning via Communication Complexity](https://mlsanity.com/paper/1402.6278/) (2014)
- [A Limitation of the PAC-Bayes Framework](https://mlsanity.com/paper/2006.13508/) (2020)
- [Characterizing the Sample Complexity of Private Learners](https://mlsanity.com/paper/1402.2224/) (2014)
- [Finite Littlestone Dimension Implies Finite Information Complexity](https://mlsanity.com/paper/2206.13257/) (2022)

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

- [The Bayesian Stability Zoo](https://mlsanity.com/paper/2310.18428/) (2023)
- [Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back](https://mlsanity.com/paper/2511.12659/) (2025)
- [Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem](https://mlsanity.com/paper/2407.07765/) (2024)
- [Private List Learnability vs. Online List Learnability](https://mlsanity.com/paper/2506.12856/) (2025)
- [Expressivity of Contradiction Graphs](https://mlsanity.com/paper/2605.20434/) (2026)

## Abstract (arXiv)

We provide a unified framework for characterizing pure and approximate differentially private (DP) learnability. The framework uses the language of graph theory: for a concept class H, we define the contradiction graph G of H. Its vertices are realizable datasets, and two datasets S,S' are connected by an edge if they contradict each other (i.e., there is a point x that is labeled differently in S and S'). Our main finding is that the combinatorial structure of G is deeply related to learning H under DP. Learning H under pure DP is captured by the fractional clique number of G. Learning H under approximate DP is captured by the clique number of G. Consequently, we identify graph-theoretic dimensions that characterize DP learnability: the clique dimension and fractional clique dimension. Along the way, we reveal properties of the contradiction graph which may be of independent interest. We also suggest several open questions and directions for future research.