Perfect Hash Family Tables

Perfect Hash Families are very extensive in combinatorial design theory literature, and have many applications to secure frame proof codes, to lookup of frequently used information, and even to my own research! There is a list of the “smallest” PHFs, located here, but has not been updated since 2006.

I am in the process of creating a “new” set of tables, not only taking into account constructions of mine (as in the last post), but also those that were published since 2006 (and there are many).

Here is a sneak peek! screen-shot-2017-03-05-at-8-25-47-pm

SoDA Talk

I will be giving a 2-talk series on my recent research work to the Software Developers’ Association at ASU on February 9 and 14th, 7:30 PM, in CAVC351. I’ll update this if there are any changes to day/time/location. It will be about new work with Covering Arrays but mostly on the optimizations in designing the suite in C++.

New Bounds for Covering Arrays of Strength 7

Happy Halloween!

I want to share some cool results of a project I’m working on in one of my classes. A covering array is a 4-tuple {CA(N; t, k, v)} which is an {N \times k} array, each entry is from an alphabet of size {v}, and for every {t} of the {k} columns, all {t}-tuples over {v} exists in at least one row when restricted to these columns. The covering array number, {CAN(t, k, v)}, is the smallest {N} for which a {CA(N; t, k, v)} exists. Kleitman and Spencer, and Katona independently, found {CAN(2, k, 2)} for all {k}; no other cases are known for all {k}, and only heuristics are known. My advisor keeps the best-known covering array numbers here. 

I was able to show the following: 

  1. {CAN(7, 10, 3) \le 4371 (-2184)},
  2. {CAN(7, 11, 3) \le 6555 (-2184)},
  3. {CAN(7, 13, 3) \le 9225 (-1698)},
  4. {CAN(7, 14, 3) \le 10923 (-2184)},
  5. {CAN(7, 15, 3) \le 13107 (-2184)},
  6. {CAN(7, 17, 5) \le 312485 (-78120)}.

The numbers in parentheses are the row reductions from previous known bounds. I won’t share how I did this yet, but it is a cool computational technique that works very well for high {t}!