Orthogonal arrays are a type of combinatorial design that were developed in
the 1940s in the design of statistical experiments. In 1947, Rao proved a lower
bound on the size of any orthogonal array, and raised the problem of
constructing arrays of minimum size. Kuperberg, Lovett and Peled (2017) gave a
non-constructive existence proof of orthogonal arrays whose size is
near-optimal (i.e., within a polynomial of Rao’s lower bound), leaving open the
question of an algorithmic construction. We give the first explicit,
deterministic, algorithmic construction of orthogonal arrays achieving
near-optimal size for all parameters. Our construction uses algebraic geometry
codes.
In pseudorandomness, the notions of