Computer Science/Discrete Mathematics Seminar I

If $x$, $y$, and $z$ are random vectors, what is the expectation of the product of their inner products, $\langle x,y \rangle$, $\langle y, z \rangle$, $\langle z, x\rangle$? If $U$ and $V$ are random unitary matrices, what is the expected trace of their commutator? Diagrammatic methods for evaluating integrals like these, which transform them into combinatorial problems, are starting to show up in computer science. I will describe three applications: showing that a simple “product of inner products” function of directed graphs is equivalent to a certain graph polynomial, showing that products of group elements in “sufficiently nonabelian” groups are nearly independent if we permute them randomly, and showing that certain estimators for the permanent, based on determinants over nonabelian algebras, have exponentially large variance.