Covering arrays and hash families

Source abstract

The explicit construction of covering arrays arises in many disparate applications in which factors or components interact. Despite this, current computational tools are effective only when the number of factors is small, while probabilistic methods are typically effective only when the number of factors is very large. Consequently combinatorial constructions have played, and continue to play, a significant role. Although some direct constructions from codes, Steiner systems, Hadamard matrices, and arrays over the finite field provide very useful examples, the workhorses of the combinatorial methods are the recursive constructions. There are two main classes of recursive techniques, the cut-and-paste or Roux-type constructions, and the column replacement techniques. After describing both for strength two, the focus is on column replacement techniques. In particular, constructions that use hash families to select columns from smaller covering arrays are examined, in order to understand the interplay among properties of the hash families and covering arrays needed to produce effective constructions. This leads to specializations both of hash families and covering arrays that merit further investigation.