报告人：Prof. Charles J. Colbourn，(Arizona State University)
报告时间：2017年5月22日下午15：00
地点：维格堂113
报告摘要: A perfect hash family PHF(N; k, w, t) is an N×k array on w symbols, in which in every N×t subarray, at least one row consists of distinct symbols (and hence separates the t columns). Perfect hash families arise in combinatorial cryptography and in constructions of covering arrays; one wants to minimize the number N of rows given that the PHF has k columns, w symbols, and strength t. Although direct constructions from codes, designs, finite geometries, and arithmetic sequences are known, the construction of specific PHF s needed in applications remains challenging.
We focus on the case when the number of rows is less than the strength. First we review a clever construction method due to Blackburn. Then we generalize his method using perfect hash families with N=t that are heterogeneous (allow differing numbers of symbols in rows) and fractal (for 1 ≤ ≤ N, every rows form a perfect hash family of strength ). Blackburn's method constructs /PHF s of larger strength from ingredients of smaller strength. Hence direct constructions and computational searches for heterogeneous, fractal PHF s of `small' strength may improve upon smallest previously known sizes for `large' strengths. We describe (1) a column exchange algorithm based on the deterministic Lov'asz local lemma; (2) a greedy column extension technique inspired by column exchange; and (3) a conditional expectation algorithm. Finally we produce many small ingredients and apply the generalization of Blackburn's approach, to establish numerous improvements on the smallest PHF s previously known.
This is joint work with Ryan Dougherty (ASU).