Heilman, Steven and Vidick, Thomas (2016) A Moment Majorization principle for random matrix ensembles with applications to hardness of the noncommutative Grothendieck problem. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20190320-103637958
![]() |
PDF
- Submitted Version
See Usage Policy. 497kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190320-103637958
Abstract
We prove a moment majorization principle for matrix-valued functions with domain {−1,1}^m, m∈N. The principle is an inequality between higher-order moments of a non-commutative multilinear polynomial with different random matrix ensemble inputs, where each variable has small influence and the variables are instantiated independently. This technical result can be interpreted as a noncommutative generalization of one of the two inequalities of the seminal invariance principle of Mossel, O'Donnell and Oleszkiewicz. Our main application is sharp Unique Games hardness for two versions of the noncommutative Grothendieck inequality. This generalizes a result of Raghavendra and Steurer who established hardness of approximation for the commutative Grothendieck inequality. A similar application was proven recently by Briët, Regev and Saket using different techniques.
Item Type: | Report or Paper (Discussion Paper) | ||||||
---|---|---|---|---|---|---|---|
Related URLs: |
| ||||||
ORCID: |
| ||||||
Additional Information: | Thanks to Todd Kemp, Elchanan Mossel, Assaf Naor, Krzysztof Oleszkiewicz, and Dimitri Shlyakhtenko for helpful discussions. | ||||||
Subject Keywords: | invariance principle, moment majorization, Lindeberg replacement, noncommutative Grothendieck inequality, Unique Games Conjecture, dictators versus low influences | ||||||
Classification Code: | 2010 Mathematics Subject Classification. 68Q17, 60E15, 47A50 | ||||||
Record Number: | CaltechAUTHORS:20190320-103637958 | ||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20190320-103637958 | ||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||
ID Code: | 93987 | ||||||
Collection: | CaltechAUTHORS | ||||||
Deposited By: | Tony Diaz | ||||||
Deposited On: | 20 Mar 2019 17:49 | ||||||
Last Modified: | 03 Oct 2019 20:59 |
Repository Staff Only: item control page