Penny-Pinching on the Coin Tosses: Designs and Association Schemes
The goal of the talk is to present my own personal view of design theory. This is likely to match the view of no one else on this planet, but I suspect it overlaps many common approaches. Starting from Gaussian quadrature in 1826, I will view designs as ways to spoof an observer, as toys for adversarial tasks in pseudorandomness. For example, if I want to convince an opponent that I am generating $k$-element subsets of a $v$-set uniformly at random, and I know that all my opponent can do is choose a fixed set $T$ of $t$ points and compute $B \cap T$ for all the samples $B$ that I generate, I see that I need only choose a $t-(v, k, \lambda)$ design and generate blocks of the design uniformly at random instead. For instance, for $v = 24$, $k = 8$, $t = 5$, this reduces each 20 coin tosses to ten.
The talk briefly reviews Gaussian quadrature and spherical $t$-designs before embarking on a tour of designs in association schemes, emphasizing a few joint projects with Doug Stinson. From the familiar - block designs and orthogonal arrays, vector space designs and designs of linear transformations - to more exotic objects such as Room squares, $\lambda$-transitive sets of permutations, ordered orthogonal arrays, and designs in sporadic $Q$-polynomial association schemes, I will mention bounds, constructions, and open problems that pique my interest. If time permits, I will discuss a connection to polynomial ideals of zero-dimensional varieties.
Bio: Bill Martin is a Professor of Mathematical Sciences and Computer Science at Worcester Polytechnic Institute. He serves on the editorial boards of BICA and JCD.