We adapt methods originally developed in information and coding theory to solve some testing problems. The efficiency of two-stage pool testing of n items is characterized by the minimum expected number E(n,p) of tests for the Bernoulli p-scheme, where the minimum is taken over a matrix that specifies the tests that constitute the first stage. An information-theoretic bound implies that the natural desire to achieve E(n,p)=o(n) as n → ∞ can be satisfied only if p(n) → 0. Using random selection and linear programming, we bound some parameters of binary matrices, thereby determining up to positive constants how the asymptotic behavior of E(n,p) as   n → ∞   depends on the manner in which    p(n) → 0.   In particular,   it is  shown   that  for   p(n)=n^-β+o(1), where 0<β<1, the asymptotic efficiency of two-stage procedures cannot be improved upon by generalizing to the class of all multistage adaptive testing algorithms.

cover-free codes, disjunctive testing, linear programming, pool testing, random selection, reconstruction algorithms, screening.

Mathematical problems and theory of numerical methods