UBC Mathematics of Information, Learning and Data Seminar: Arvin Sahami

The design of statistical experiments is a classical topic in statistics, dating back to work of Fisher in the 1930s. One of the mathematical objects used to plan experiments is an "orthogonal array", defined by C. R. Rao. In 1947, Rao proved that every orthogonal array must have at least (c*m*n/t)^{c*t} rows, where m is the number of factors, n is the number of levels, t is the strength, and c is a universal constant. He raised the problem of constructing such arrays.

76 years later, we give the first explicit construction of an orthogonal array with (c*m*n/t)^{c*t} rows, for all parameters m, n, t. This matches Rao's lower bound, with a different constant c. The array can be constructed by a deterministic, polynomial time algorithm.

Joint work with Nick Harvey.