Gebhard, OliverOliverGebhardHahn-Klimroth, MaxMaxHahn-KlimrothKaaser, DominikDominikKaaserLoick, PhilippPhilippLoick2023-04-052023-04-052022Proceedings - 2022 IEEE 36th International Parallel and Distributed Processing Symposium, IPDPS 2022 (): 425-435 (2022)http://hdl.handle.net/11420/15129In the pooled data problem the goal is to efficiently reconstruct a binary signal from additive measurements. Given a signal sigmain 0, 1n, we can query multiple entries at once and get the total number of non-zero entries in the query as a result. We assume that queries are time-consuming and therefore focus on the setting where all queries are executed in parallel. For the regime where the signal is sparse such that VertsigmaVert₁= o(n) our results are twofold: First, we propose and analyze a simple and efficient greedy reconstruction algorithm. Secondly, we derive a sharp information-theoretic threshold for the minimum number of queries required to reconstruct s with high probability. Our first result matches the performance guarantees of much more involved constructions (Karimi et al. 2019). Our second result extends a result of Alaoui et al. (2014) and Scarlett & Cevher (2017) who studied the pooled data problem for dense signals. Finally, our theoretical findings are complemented with empirical simulations. Our data not only confirm the information-theoretic thresholds but also hint at the practical applicability of our pooling scheme and the simple greedy reconstruction algorithm.enInformation TheoryPhase TransitionsPooled DataReconstructionSparse SignalInformatikConference Paper10.1109/IPDPS53621.2022.00048Conference Paper