Quickly-Decodable Group Testing with Fewer Tests: Price-Scarlett and Cheraghchi-Nakos's Nonadaptive Splitting with Explicit Scalars

We modify Cheraghchi-Nakos [CN20] and Price-Scarlett's [PS20] fast binary splitting approach to nonadaptive group testing. We show that, to identify a uniformly random subset of k infected persons among a population of n, it takes only ln(2 - 4ε) ⁻² k ln n tests and decoding complexity O(ε⁻² k ln n), for any small ε > 0, with vanishing error probability. In works prior to ours, only two types of group testing schemes exist. Those that use ln(2)⁻² k ln n or fewer tests require linear-in-n complexity, sometimes even polynomial in n; those that enjoy sub-n complexity employ O(k ln n) tests, where the big-O scalar is implicit, presumably greater than ln(2)⁻². We almost achieve the best of both worlds, namely, the almost-ln(2)⁻² scalar and the sub-n decoding complexity. How much further one can reduce the scalar ln(2)⁻² remains an open problem.