Almost-Orthogonal Bases for Inner Product Polynomials

Abstract

We consider low-degree polynomials of inner products between a collection of random vectors. We give an explicit, almost-orthogonal basis for this vector space of polynomials when the random vectors are Gaussian, spherical, or Boolean. In all three cases, our basis admits an interesting combinatorial description based on the topology of the underlying graph of inner products. In the spherical case, interesting examples suggest a connection to graph planarity. Based on joint work with Aaron Potechin.