Explicit Orthogonal and Unitary Designs

Explore a one-hour lecture by Ryan O'Donnell from Carnegie Mellon University on explicit orthogonal and unitary designs, presented at the Simons Institute as part of the "Beyond the Boolean Cube" series. Delve into a strongly explicit construction of 𝜖-approximate 𝑘-designs for the orthogonal group O(𝑁) and the unitary group U(𝑁), where 𝑁 = 2ⁿ. Learn about designs with cardinality poly(𝑁ᵏ/𝜖) and seed length 𝑂(𝑛𝑘 + log(1/𝜖)), which closely match the number of design elements used in completely random matrix constructions. Gain insights into this joint work with Pedro Paredes (Princeton) and Rocco Servedio (Columbia), advancing understanding in the field of mathematical designs and group theory.

Explicit Orthogonal and Unitary Designs