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

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.

Files

Additional details