Explicit Orthogonal and Unitary Designs

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=uq5PFqPZMK4


Duration: 1:00:15
760 views
19

Ryan O'Donnell (Carnegie Mellon University)
https://simons.berkeley.edu/talks/ryan-odonnell-carnegie-mellon-university-2023-06-26
Beyond the Boolean Cube

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).



Other Videos By Simons Institute for the Theory of Computing


2023-06-29ErdΕ‘s and Shannon: A Story of Probability, Communication, and Combinatorics
2023-06-29Fractional Pseudorandom Generators
2023-06-29Strong Bounds for 3-Progressions
2023-06-28Parallel Discrete Sampling via Continuous Walks
2023-06-28Unique Games and Expansion
2023-06-28Small-Set Expansion in the 2-Degree Short-Code Graph, the Easier Version
2023-06-27Product Mixing, Quantum Separation, and Comfortable Juntas
2023-06-27Explicit SoS Lower Bounds from (Small-Set) High Dimensional Expanders
2023-06-27Hypercontractivity Inequality on $\varepsilon$-product Spaces
2023-06-27Reverse Hypercotractivity and Improved Sampling in High Dimensional Expanders
2023-06-26Explicit Orthogonal and Unitary Designs
2023-06-20Simons Institute Live Stream
2023-06-14Computer Vision after the Victory of Data
2023-06-14Communication in the Service of Coordinated Action by Spotted Hyenas
2023-06-14Do Elephants Have Names? Vocal Labeling of Individual Conspecifics in African Elephants + ...
2023-06-14Generative AI and What Is Meaningful Sperm Whale Communication
2023-06-14GPT-Whale Language Models at Tools for Structure Discovery and Hypothesis Generation
2023-06-13Deep Emergent Communication: How It Started and How It’s Going
2023-06-13Decoding Dolphin Communication
2023-06-13Structural Transfer Learning: Exploring Neural Models and Language Structure Through...
2023-06-13Individual Discrimination of Bottlenose Dolphin Signature Whistles Using Deep Learning


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Beyond the Boolean Cube
Ryan O'Donnell