Name
Title | ||
|---|---|---|
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\in\mathbb{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\"{e}t, Regev and Saket using different techniques. |
Year | Venue | Field |
|---|---|---|
2016 | arXiv: Functional Analysis | Noncommutative geometry,Topology,Combinatorics,Invariance principle,Commutative property,Mathematical analysis,Hardness of approximation,Multilinear polynomial,Majorization,Grothendieck inequality,Mathematics,Random matrix |
DocType | Volume | Citations |
Journal | abs/1603.05620 | 0 |
PageRank | References | Authors |
0.34 | 8 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Steven Heilman | 1 | 0 | 0.68 |
| Thomas Vidick | 2 | 377 | 31.69 |