# Sample completion, structured correlation, and Netflix problems

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Sep 2025.

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

- [Higher-arity PAC learning, VC dimension and packing lemma](https://mlsanity.com/paper/2510.02420/) (2025)
- [Remarks on a recent preprint of Chernikov and Towsner](https://mlsanity.com/paper/2510.19665/) (2025)

## Abstract (arXiv)

We develop a new high-dimensional statistical learning model which can take advantage of structured correlation in data even in the presence of randomness. We completely characterize learnability in this model in terms of VCNk,k-dimension (essentially k-dependence from Shelah's classification theory). This model suggests a theoretical explanation for the success of certain algorithms in the 2006~Netflix Prize competition.