Probability Seminar

Date: December 5, 2016

Time: 3:00PM - 4:00PM

Location: BLOC 628

Speaker: Steven Heilman, UCLA

Title: Noncommutative Majorization Principles and Grothendieck's Inequality

Abstract: The seminal invariance principle of Mossel-O'Donnell-Oleszkiewicz implies the following. Suppose we have a multilinear polynomial Q, all of whose partial derivatives are small. Then the distribution of Q on i.i.d. uniform {-1,1} inputs is close to the distribution of Q on i.i.d. standard Gaussian inputs. The case that Q is a linear function recovers the Berry-Esseen Central Limit Theorem. In this way, the invariance principle is a nonlinear version of the Central Limit Theorem. We prove the following version of one of the two inequalities of the invariance principle, which we call a majorization principle. Suppose we have a multilinear polynomial Q with matrix coefficients, all of whose partial derivatives are small. Then, for any even K>1, the Kth moment of Q on i.i.d. uniform {-1,1} inputs is larger than the Kth moment of Q on (carefully chosen) random matrix inputs, minus a small number. The exact statement must be phrased carefully in order to avoid being false. Time permitting, we discuss applications of this result to anti-concentration, and to computational hardness for the noncommutative Grothendieck inequality. (joint with Thomas Vidick) https://arxiv.org/abs/1603.05620