Speaker: 

Steven Heilman

Institution: 

UCLA

Time: 

Tuesday, November 29, 2016 - 11:00pm to 11:50pm

Host: 

Location: 

RH 306

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) (