Almost-Orthogonal Bases for Inner Product Polynomials

Chris Jones University of Chicago


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.

Feb 22, 2022 3:30 PM — Jan 25, 2022 5:00 PM
Theory Seminar