Group testing is a long studied problem in combinatorics: A small set ofrill people should be identified out of the whole (npeople) by using only queries (tests) of the form “Does set X contain an ill human?” In this paper we provide an explicit construction of a testing scheme which is better (smaller) than any known explicit construction. This scheme has Θ(min[r2lnn,n]) tests which is as many as the best nonexplicit schemes have. In our construction, we use a fact that may have a value by its own right: Linear error-correction codes with parameters [m,k,δm]qmeeting the Gilbert-Varshamov bound may be constructed quite efficiently, in Θ(qkm) time.

We consider the classic problem of pattern matching with few mismatches in the presence of promiscuously matching wildcard symbols. Given a text t of length n and a pattern p of length m with optional wildcard symbols and a bound k, our algorithm finds all the alignments for which the pattern matches the text with Hamming distance at most k and also returns the location and identity of each mismatch. The algorithm we present is deterministic and runs in Õ(kn) time, matching the best known randomised time complexity to within logarithmic factors. The solutions we develop borrow from the tool set of algebraic coding theory and provide a new framework in which to tackle approximate pattern matching problems.