We give a strongly explicit construction of ๐œ–-approximate ๐‘˜-designs for the orthogonal group O(๐‘) and the unitary group U(๐‘), for ๐‘ = 2โฟ. Our designs are of cardinality poly(๐‘แต/๐œ–) (equivalently, they have seed length ๐‘‚(๐‘›๐‘˜ + log(1/๐œ–))); up to the polynomial, this matches the number of design elements used by the construction consisting of completely random matrices.

Joint work with Pedro Paredes (Princeton) and Rocco Servedio (Columbia).


Video Recording