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, pp. 1240-1260.


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.

Link to full version

pdf of conference version


Back to main papers page