Via Zoom: Graph Matrices: Norm Bounds and Applications

Wednesday, April 1, 2020 - 4:00pm to 4:30pm

Event Calendar Category

LIDS & Stats Tea

Speaker Name

Kwangjun Ahn




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.  


Kwangjun Ahn is a graduate student in EECS and LIDS. His research interests include Optimization, Probability and Statistics, and Random Matrix Theory.

Join Zoom Meeting

Meeting ID: 191 083 545

Join by SIP


Join by Skype for Business