Explicit orthogonal and unitary designs

Ryan O'Donnell, Rocco A. Servedio, Pedro Paredes

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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

Original languageEnglish (US)
Title of host publicationProceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023
PublisherIEEE Computer Society
Pages1240-1260
Number of pages21
ISBN (Electronic)9798350318944
DOIs
StatePublished - 2023
Event64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023 - Santa Cruz, United States
Duration: Nov 6 2023Nov 9 2023

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Conference

Conference64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023
Country/TerritoryUnited States
CitySanta Cruz
Period11/6/2311/9/23

All Science Journal Classification (ASJC) codes

  • General Computer Science

Keywords

  • pseudorandomness

Fingerprint

Dive into the research topics of 'Explicit orthogonal and unitary designs'. Together they form a unique fingerprint.

Cite this