  We consider the probabilistic group testing problem where $d$ random
defective items in a large population of $N$ items are identified with high
probability by applying binary tests. It is known that $\Theta(d \log N)$ tests
are necessary and sufficient to recover the defective set with vanishing
probability of error when $d = O(N^{\alpha})$ for some $\alpha \in (0, 1)$.
However, to the best of our knowledge, there is no explicit (deterministic)
construction achieving $\Theta(d \log N)$ tests in general. In this work, we
show that a famous construction introduced by Kautz and Singleton for the
combinatorial group testing problem (which is known to be suboptimal for
combinatorial group testing for moderate values of $d$) achieves the order
optimal $\Theta(d \log N)$ tests in the probabilistic group testing problem
when $d = \Omega(\log^2 N)$. This provides a strongly explicit construction
achieving the order optimal result in the probabilistic group testing setting
for a wide range of values of $d$. To prove the order-optimality of Kautz and
Singleton's construction in the probabilistic setting, we provide a novel
analysis of the probability of a non-defective item being covered by a random
defective set directly, rather than arguing from combinatorial properties of
the underlying code, which has been the main approach in the literature.
Furthermore, we use a recursive technique to convert this construction into one
that can also be efficiently decoded with only a log-log factor increase in the
number of tests.
