# On a Near-Optimal & Efficient Algorithm for the Sparse Pooled Data Problem

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 30 references that are in the map.
- First posted on arXiv 22 Dec 2023.

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

- [The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics](https://mlsanity.com/paper/2205.09727/) (2022)
- [Optimal Low-Degree Hardness of Maximum Independent Set](https://mlsanity.com/paper/2010.06563/) (2020)
- [Statistical and Computational Phase Transitions in Group Testing](https://mlsanity.com/paper/2206.07640/) (2022)
- [Neural Group Testing to Accelerate Deep Learning](https://mlsanity.com/paper/2011.10704/) (2020)
- [Decoding from Pooled Data: Phase Transitions of Message Passing](https://mlsanity.com/paper/1702.02279/) (2017)
- [Phase Transitions in the Pooled Data Problem](https://mlsanity.com/paper/1710.06766/) (2017)
- [Support Recovery in Universal One-bit Compressed Sensing](https://mlsanity.com/paper/2107.09091/) (2021)
- [Optimal Nested Test Plan for Combinatorial Quantitative Group Testing](https://mlsanity.com/paper/1407.2283/) (2014)
- [Optimal Design of Process Flexibility for General Production Systems](https://mlsanity.com/paper/1806.02894/) (2018)

## Abstract (arXiv)

The pooled data problem asks to identify the unknown labels of a set of items from condensed measurements. More precisely, given n items, assume that each item has a label in cbc0,1,ldots, d, encoded via the ground-truth SIGMA. We call the pooled data problem sparse if the number of non-zero entries of SIGMA scales as k ~ nθ for θ ∈ (0,1). The information that is revealed about SIGMA comes from pooled measurements, each indicating how many items of each label are contained in the pool. The most basic question is to design a pooling scheme that uses as few pools as possible, while reconstructing SIGMA with high probability. Variants of the problem and its combinatorial ramifications have been studied for at least 35 years. However, the study of the modern question of efficient inference of the labels has suggested a statistical-to-computational gap of order log n in the minimum number of pools needed for theoretically possible versus efficient inference. In this article, we resolve the question whether this log n-gap is artificial or of a fundamental nature by the design of an efficient algorithm, called algoname, based upon a novel pooling scheme on a number of pools very close to the information-theoretic threshold.