Via Zoom: Graph Matrices: Norm Bounds and Applications

Graph matrices are a type of random matrix which has the following properties: (i) The entries of the matrix depend on random input. Moreover, this dependence can be described by a small graph. (ii) The matrix (as a function of the input) is symmetric under permutations of [n]. Graph matrices are important objects to study because they are closely connected to the Sum of Squares (SoS) hierarchy, one of the most powerful techniques we know of for solving combinatorial optimization problems as well as inference problems arising from physics and machine learning. However, since graph matrices generally have dependent entries, they are not captured by current results in random matrix theory. In this talk, we use the trace power method to give a general norm bound on all graph matrices which is accurate up to polylogarithmic factors. We then describe several applications of graph matrices where approaches based on graph matrices simplify the original analyses of spectral algorithms and SoS algorithms.