3 papers
cs.IT2026
Algorithms for Threshold Group Testing
Amin Coja-Oghlan, Remco van der Hofstad, Lena Krieg +3
We study the Threshold Group Testing (TGT) problem without a gap in the noiseless, non-adaptive setting, where the goal is to exactly recover a sparse binary vector from pooled tes…
math.CO2025
Belief Propagation Guided Decimation on Random k-XORSAT
Arnab Chatterjee, Amin Coja-Oghlan, Mihyun Kang +3
We analyse the performance of Belief Propagation Guided Decimation, a physics-inspired message passing algorithm, on the random -XORSAT problem. Specifically, we derive an expli…
cs.DM2024
Noisy Linear Group Testing: Exact Thresholds and Efficient Algorithms
Lukas Hintze, Lena Krieg, Olga Scheftelowitsch +1
In group testing, the task is to identify defective items by testing groups of them together using as few tests as possible. We consider the setting where each item is defective wi…