4 papers
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…
An Information-Theoretic Analysis of Threshold Group Testing
Remco van der Hofstad, Noela Müller, Connor Riddlesden
We study the Threshold Group Testing (TGT) problem in the noiseless and non-adaptive setting, where the objective is to exactly recover a sparse binary vector from pooled tests, us…
The number of random 2-SAT solutions is asymptotically log-normal
Arnab Chatterjee, Amin Coja-Oghlan, Noela Müller +4
We prove that throughout the satisfiable phase, the logarithm of the number of satisfying assignments of a random 2-SAT formula satisfies a central limit theorem. This implies that…
On a Near-Optimal \& Efficient Algorithm for the Sparse Pooled Data Problem
Max Hahn-Klimroth, Remco van der Hofstad, Noela Müller +1
The pooled data problem asks to identify the unknown labels of a set of items from condensed measurements. More precisely, given items, assume that each item has a label in $\c…