A semi-random construction of small covering arrays

Abstract: 

Given a set SS of v≥2v≥2 symbols, and integers k≥t≥2k≥t≥2 and N≥1N≥1,  an N×kN×k array A∈SN×kA∈SN×k is an (N;t,k,v)(N;t,k,v)-covering array if all sequences in StSt appear as rows in every N×tN×t subarray of AA.

These arrays have a wide variety of applications, driving the search for small covering arrays. The covering array number, CAN(t,k,v)(t,k,v), is the smallest NN for which an (N;t,k,v)(N;t,k,v)-covering array exists.  In this talk we shall combine probabilistic and algebraic arguments to construct small covering arrays, improving the bounds on CAN(t,k,v)CAN(t,k,v).