Explicit orthogonal and unitary designs.
R. O'Donnell and R. Servedio and P. Paredes (*) Author ordering randomized.
In 64th Annual Symposium on Foundations of Computer Science (FOCS), 2023, to appear.


Abstract:

We give a strongly explicit construction of $\eps$-approximate $k$-designs for the orthogonal group~$\Ogp{N}$ and the unitary group~$\Ugp{N}$, for $N=2^n$. Our designs are of cardinality~$\poly(N^k/\eps)$ (equivalently, they have seed length $O(nk + \log(1/\eps)))$; up to the polynomial, this matches the number of design elements used by the construction consisting of completely random matrices.


Back to main papers page