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.

本文研究了一个大型项目中标记的识别问题，包括无噪声和有噪声的情况及基于统计学的准确性要求。作者们给出了阈值，并证明了成功率和失败率之间的过渡现象。此外，本文提出了一种对于一般随机噪声模型的多样化信息理论框架，以表征所需的测试数量，研究结果表明即使在低噪声水平下噪声都能使问题变得更加困难，最后通过一个近似恢复问题证明了与标签解码中允许一定数量的误差存在类似的行为。

汇总数据问题中的相变现象