# Expressivity of Contradiction Graphs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 27 references that are in the map.
- First posted on arXiv 19 May 2026.

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

- [Private Learning and Sanitization: Pure vs. Approximate Differential Privacy](https://mlsanity.com/paper/1407.2674/) (2014)
- [Sample Complexity Bounds on Differentially Private Learning via Communication Complexity](https://mlsanity.com/paper/1402.6278/) (2014)
- [Sample-efficient proper PAC learning with approximate differential privacy](https://mlsanity.com/paper/2012.03893/) (2020)
- [The Bayesian Stability Zoo](https://mlsanity.com/paper/2310.18428/) (2023)
- [A Unified Characterization of Private Learnability via Graph Theory](https://mlsanity.com/paper/2304.03996/) (2023)
- [Private PAC Learning May be Harder than Online Learning](https://mlsanity.com/paper/2402.11119/) (2024)

## Abstract (arXiv)

We study the contradiction graphs associated with a binary concept class. For a class Hsubseteq0,1X, the order-m contradiction graph Gm(H) has as vertices the H-realizable labeled sequences of length m, with two vertices adjacent when the two sequences assign opposite labels to some common domain point. First, we identify a graph-theoretic property that determines the threshold predicate operatornameVCdim(H)≥ m. Consequently, the sequence (Gm(H))m≥1 determines the exact VC dimension and, in particular, distinguishes finite from infinite VC dimension, answering a question posed by Alon et al. (2024). We then generalize this result by proving that the sequence of contradiction graphs determines, up to signed relabeling, the realizable datasets of any fixed length. Thus, any learning-theoretic property determined by the realizable datasets of a fixed length and invariant under signed relabeling can be recovered from the contradiction graph sequence. As an application, we explicitly provide a characterization of Littlestone dimension.