2026-07-19T19:44:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23705 2025-10-27T10:42:38Z ddc:004 open_access

Switching Graph Matrix Norm Bounds: From i.i.d. to Random Regular Graphs Xu, Jeff Semidefinite programming random matrices average-case complexity 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 average-case algorithms and hardness. Previous investigations of such matrices are largely restricted to the Erdős-Rényi model, and tight matrix norm bounds on regular graphs are only known for specific examples. We unite these two lines of investigations, and give the first result departing from the Erdős-Rényi setting in the full generality of graph matrices. We believe our norm bound result would enable a simple transfer of spectral analysis for average-case algorithms and hardness between these two distributions of random graphs. As an application of our spectral norm bounds, we show that higher-degree Sum-of-Squares lower bounds for the independent set problem on Erdős-Rényi random graphs can be switched into lower bounds on random d-regular graphs. Our main conceptual insight is that existing Sum-of-Squares lower bounds analysis based on moment methods are surprisingly robust, and amenable for a light-weight translation. Our result is the first to address the general open question of analyzing higher-degree Sum-of-Squares on random regular graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jeff Xu 2025 Is Part Of LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2025.11 urn:nbn:de:0030-drops-237054 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.11 eng https://creativecommons.org/licenses/by/4.0/legalcode