# Phase Transitions in the Pooled Data Problem

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

## Key facts

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

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

- [Learning from Label Proportions: Bootstrapping Supervised Learners via Belief Propagation](https://mlsanity.com/paper/2310.08056/) (2023)
- [Distributed Reconstruction of Noisy Pooled Data](https://mlsanity.com/paper/2204.07491/) (2022)
- [Efficient Neural Network based Classification and Outlier Detection for Image Moderation using Compressed Sensing and Group Testing](https://mlsanity.com/paper/2305.07639/) (2023)
- [Efficient Approximate Recovery from Pooled Data Using Doubly Regular Pooling Schemes](https://mlsanity.com/paper/2303.00043/) (2023)
- [On a Near-Optimal & Efficient Algorithm for the Sparse Pooled Data Problem](https://mlsanity.com/paper/2312.14588/) (2023)
- [Verifiable Deep Quantitative Group Testing](https://mlsanity.com/paper/2512.07279/) (2025)

## Abstract (arXiv)

In this paper, we study the pooled data problem of identifying the labels associated with a large collection of items, based on a sequence of pooled tests revealing the counts of each label within the pool. In the noiseless setting, we identify an exact asymptotic threshold on the required number of tests with optimal decoding, and prove a phase transition between complete success and complete failure. In addition, we present a novel noisy variation of the problem, and provide an information-theoretic framework for characterizing the required number of tests for general random noise models. Our results reveal that noise can make the problem considerably more difficult, with strict increases in the scaling laws even at low noise levels. Finally, we demonstrate similar behavior in an approximate recovery setting, where a given number of errors is allowed in the decoded labels.