Speaker: Charles J. Colbourn，Arizona State University
Time: 20170515 16:0017:00
Place： Room 1418, School of Mathematical Sciences
Detail：
Covering arrays are used to test the correctness of
complex engineered systems with k components each having v options, when
collections of at most t component options can cause failures. Of most interest
are cases when 2 ≤
t ≤ 6 and 2 ≤ v ≤ 10, but k can be quite large, perhaps in the hundreds or thousands.
The construction of covering arrays with few tests is a challenging
mathematical and computational problem. Covering perfect hash families
represent certain covering arrays compactly. In this talk we describe how
covering perfect hash families lead to an improvement upon the best known
asymptotic upper bound for the minimum number of tests (rows) in a covering
array with v symbols, k columns, and strength t. We then show that the compact
representation makes the computation of ‘large’ covering arrays meeting the new bound feasible: One method uses the
deterministic Lov′asz local lemma, another uses a
conditional expectation approach. For example, we report on improved bounds for
covering arrays of strength 3 with k ≤ 10000, and
demonstrate that the methods remain feasible even for strength 7, for which no
explicit computational results have earlier been reported.We close by outlining
connections with ﬁnite ﬁelds and ﬁnite geometry, and
suggestsome important next steps.This is joint work with Erin Lanus and Kaushik
Sarkar (ASU).
Organizer: School of Mathematical Sciences
