# Concomitant Group Testing

arXiv: https://arxiv.org/abs/2309.04221 · HTML: https://mlsanity.com/paper/2309.04221/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 56 references that are in the map.
- First posted on arXiv 8 Sep 2023.

## Builds on (most cited first, 6 of 6)

- [On Learning Graphs with Edge-Detecting Queries](https://mlsanity.com/paper/1803.10639/) (2018)
- [Decoding from Pooled Data: Phase Transitions of Message Passing](https://mlsanity.com/paper/1702.02279/) (2017)
- [A Fast Binary Splitting Approach to Non-Adaptive Group Testing](https://mlsanity.com/paper/2006.10268/) (2020)
- [Combinatorial Group Testing and Sparse Recovery Schemes with Near-Optimal Decoding Time](https://mlsanity.com/paper/2006.08420/) (2020)
- [Sublinear-Time Non-Adaptive Group Testing with O(k log n) Tests via Bit-Mixing Coding](https://mlsanity.com/paper/1904.10102/) (2019)
- [AC-DC: Amplification Curve Diagnostics for Covid-19 Group Testing](https://mlsanity.com/paper/2011.05223/) (2020)

## Abstract (arXiv)

In this paper, we introduce a variation of the group testing problem capturing the idea that a positive test requires a combination of multiple ``types'' of item. Specifically, we assume that there are multiple disjoint semi-defective sets, and a test is positive if and only if it contains at least one item from each of these sets. The goal is to reliably identify all of the semi-defective sets using as few tests as possible, and we refer to this problem as textitConcomitant Group Testing (ConcGT). We derive a variety of algorithms for this task, focusing primarily on the case that there are two semi-defective sets. Our algorithms are distinguished by (i) whether they are deterministic (zero-error) or randomized (small-error), and (ii) whether they are non-adaptive, fully adaptive, or have limited adaptivity (e.g., 2 or 3 stages). Both our deterministic adaptive algorithm and our randomized algorithms (non-adaptive or limited adaptivity) are order-optimal in broad scaling regimes of interest, and improve significantly over baseline results that are based on solving a more general problem as an intermediate step (e.g., hypergraph learning).