CaltechAUTHORS
  A Caltech Library Service

A Moment Majorization principle for random matrix ensembles with applications to hardness of the noncommutative Grothendieck problem

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

[img] PDF - Submitted Version
See Usage Policy.

485Kb

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:
URLURL TypeDescription
https://arxiv.org/abs/1603.05620arXivDiscussion Paper
ORCID:
AuthorORCID
Vidick, Thomas0000-0002-6405-365X
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