Covering Perfect Hash Families

  • [2017-05-15]

    Speaker: Charles J. Colbourn,Arizona State University

    Time:    2017-05-15  16:00-17:00

    Place:  Room 1418, School of Mathematical Sciences 


    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).

    Organizer: School of Mathematical Sciences



Highlight of USTC

According to the latest Nature Publishing Index (NPI) Asia-Pacific and The Nature Publishing Index China, University of Science and Technology of China tops in Chinese universities again. The rankings are based on the number of papers that were published in Nature journals during the last 12 months.


This article came from News Center of USTC.