![Analysis and TCS_hi-res_logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-02/Analysis%20and%20TCS_hi-res.png.jpg?itok=HyceKiAM)
Abstract
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).