A Semi-Random Construction of Small Covering Arrays

Abstract

Given a set $S$ of $v\ge 2$ symbols, and integers $k\ge t\ge 2$ and $N\ge 1$, an $N\times k$ array $A\in S^{N\times k}$ is an $(N;t,k,v)$-covering array if all sequences in $S^t$ appear as rows in every $N\times t$ subarray of $A$. These arrays have a wide variety of applications, driving the search for small covering arrays. The covering array number, $\mathrm{CAN}(t,k,v)$, is the smallest $N$ for which an $(N;t,k,v)$-covering array exists. In this paper, we combine probabilistic and linear algebraic constructions to improve the upper bounds on $\mathrm{CAN}(t,k,v)$ by a factor of $\ln v$, showing that for prime powers $v$, $\mathrm{CAN}(t,k,v)\le (1+o(1))\left((t-1)v^t/(2{\log }_{2}v-{\log }_2(v+1))\right){\log }_{2}k$, which also offers improvements for large $v$ that are not prime powers. Our main tool, which may be of independent interest, is a construction of an array with $v^t$ rows that covers the maximum possible number of subsets of size $t$.

20 pages. This version subsumes the results in the previous version, "Families of Mass Destruction," generalising the results from set systems to covering arrays over larger alphabets