We consider the problem of decoding a discrete signal of categorical variables from the observation of several histograms of pooled subsets of it: A population of consisting of n individuals, where each individual belongs to one category among d, is queried. In each query, a subset of individuals is selected, and the histogram of their types, along with the individuals in that subset are revealed. We study the problem in  the "random dense" setting where each query involves a random subset of individuals of size proportional to n. We discuss the information-theoretic question of signal identifiability from a minimal number of measurements, and present a message-passing algorithm for recovering the signal and characterize its exact asymptotic behavior. The analysis reveals a gap between what is statistically possible and what is achieved by our algorithm.  
Based on arxiv:1611.09981, arxiv:1702.02279