Title: Covering Perfect Hash Families

Speaker: Charles J. Colbourn (Arizona State University)

Time: 5.15 4:00-5:00

Place: 1518

Abstract: 

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 finite fields and finite geometry, and suggestsome important next steps.This is joint work with Erin Lanus and Kaushik Sarkar (ASU).