# Computational Implications of Reducing Data to Sufficient Statistics

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Sep 2014.

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

- [Learning quantum Hamiltonians at any temperature in polynomial time](https://mlsanity.com/paper/2310.02243/) (2023)
- [Provable benefits of score matching](https://mlsanity.com/paper/2306.01993/) (2023)
- [Local Diffusion Models and Phases of Data Distributions](https://mlsanity.com/paper/2508.06614/) (2025)
- [Solution Path of Time-varying Markov Random Fields with Discrete Regularization](https://mlsanity.com/paper/2307.13750/) (2023)
- [Computationally sufficient statistics for Ising models](https://mlsanity.com/paper/2602.12449/) (2026)
- [Finite Sample Bounds for Learning with Score Matching](https://mlsanity.com/paper/2605.14168/) (2026)

## Abstract (arXiv)

Given a large dataset and an estimation task, it is common to pre-process the data by reducing them to a set of sufficient statistics. This step is often regarded as straightforward and advantageous (in that it simplifies statistical analysis). I show that -on the contrary- reducing data to sufficient statistics can change a computationally tractable estimation problem into an intractable one. I discuss connections with recent work in theoretical computer science, and implications for some techniques to estimate graphical models.