Switching Graph Matrix Norm Bounds: from i.i.d. to Random Regular Graphs
Switching Graph Matrix Norm Bounds: from i.i.d. to Random Regular Graphs
In this work, we give novel spectral norm bounds for graph matrix on inputs being random regular graphs. Graph matrix is a family of random matrices with entries given by polynomial functions of the underlying input. These matrices have been known to be the backbone for the analysis of various …