A semi-random construction of small covering arrays

Speaker: 

Tamás Mészáros

Affiliation: 

Freie Universität Berlin

Date: 

Mon, 11/12/2017 - 11:00am

Venue: 

RC-4082, The Red Centre, UNSW

Abstract: 

Given a set $S$ of $v\geq 2$ symbols, and integers $k \geq t \geq 2$ and $N \geq 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, CAN$(t,k,v)$, is the smallest $N$ for which an $(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)$.

 

School Seminar Series: