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}!