搜索:
 
 当前位置:>首页 -> Events
Covering Perfect Hash Families
·······················································································································································································································································

Speaker: Charles J. ColbournArizona State University

Time:    2017-05-15  16:00-17: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 Lovasz 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

  网站首页 | 学院概况 | 院系介绍 | 新闻中心 | 师资队伍 | 科学研究 | 人才培养 | 学科建设 | 学生工作 | 研招在线 | 资料下载   2011 中国科学技术大学数学科学学院
站点维护: yangor