A Semi-Random Construction of Small Covering Arrays

Abstract: Given a set

S

of

v g e 2

symbols, and integers

k g e t g e 2

and

N g e 1

, an

N i m e s k

array

A i n S^{N i m e s k}

is an

(N; t, k, v)

-covering array if all sequences in

S^{t}

appear as rows in every

N i m e s t

subarray of

A

. These arrays have a wide variety of applications, driving the search for small covering arrays. The covering array number,

m a t h r m C A N (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

m a t h r m C A N (t, k, v)

by a factor of

l n v

, showing that for prime powers

v

,

m a t h r m C A N (t, k, v) l e (1 + o (1)) l e f t ((t - 1) v^{t} / (2 l o g_{2} v - l o g_{2} (v + 1)) i g h t) l o g_{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

.

This page was built for publication: A Semi-Random Construction of Small Covering Arrays