TY - GEN

T1 - Sum-of-Squares Lower Bounds for Independent Set on Ultra-Sparse Random Graphs

AU - Kothari, Pravesh K.

AU - Potechin, Aaron

AU - Xu, Jeff

N1 - Publisher Copyright:
© 2024 Owner/Author.

PY - 2024/6/10

Y1 - 2024/6/10

N2 - We prove that for every D ∈ N, and large enough constant d ∈ N, with high probability over the choice of G ∼G(n,d/n), the Erdos-Renyi random graph distribution, the canonical degree 2D Sum-of-Squares relaxation fails to certify that the largest independent set in G is of size o(n/√d D4). In particular, degree D sum-of-squares strengthening can reduce the integrality gap of the classical theta SDP relaxation by at most a O(D4) factor. This is the first lower bound for >4-degree Sum-of-Squares (SoS) relaxation for any problems on ultra sparse random graphs (i.e. average degree of an absolute constant). Such ultra-sparse graphs were a known barrier for previous methods and explicitly identified as a major open direction. Indeed, the only other example of an SoS lower bound on ultra-sparse random graphs was a degree-4 lower bound for Max-Cut. Our main technical result is a new method to obtain spectral norm estimates on graph matrices (a class of low-degree matrix-valued polynomials in G(n,d/n)) that are accurate to within an absolute constant factor. All prior works lose log n factors that trivialize any lower bound on o(logn)-degree random graphs. We combine these new bounds with several upgrades on the machinery for analyzing lower-bound witnesses constructed by pseudo-calibration so that our analysis does not lose any ω(1)-factors that would trivialize our results. In addition to other SoS lower bounds, we believe that our methods for establishing spectral norm estimates on graph matrices will be useful in the analyses of numerical algorithms on average-case inputs.

AB - We prove that for every D ∈ N, and large enough constant d ∈ N, with high probability over the choice of G ∼G(n,d/n), the Erdos-Renyi random graph distribution, the canonical degree 2D Sum-of-Squares relaxation fails to certify that the largest independent set in G is of size o(n/√d D4). In particular, degree D sum-of-squares strengthening can reduce the integrality gap of the classical theta SDP relaxation by at most a O(D4) factor. This is the first lower bound for >4-degree Sum-of-Squares (SoS) relaxation for any problems on ultra sparse random graphs (i.e. average degree of an absolute constant). Such ultra-sparse graphs were a known barrier for previous methods and explicitly identified as a major open direction. Indeed, the only other example of an SoS lower bound on ultra-sparse random graphs was a degree-4 lower bound for Max-Cut. Our main technical result is a new method to obtain spectral norm estimates on graph matrices (a class of low-degree matrix-valued polynomials in G(n,d/n)) that are accurate to within an absolute constant factor. All prior works lose log n factors that trivialize any lower bound on o(logn)-degree random graphs. We combine these new bounds with several upgrades on the machinery for analyzing lower-bound witnesses constructed by pseudo-calibration so that our analysis does not lose any ω(1)-factors that would trivialize our results. In addition to other SoS lower bounds, we believe that our methods for establishing spectral norm estimates on graph matrices will be useful in the analyses of numerical algorithms on average-case inputs.

KW - Average-case complexity

KW - Random Matrix Theory

KW - Sum-of-Squares Lower Bounds

UR - http://www.scopus.com/inward/record.url?scp=85196615388&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85196615388&partnerID=8YFLogxK

U2 - 10.1145/3618260.3649703

DO - 10.1145/3618260.3649703

M3 - Conference contribution

AN - SCOPUS:85196615388

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 1923

EP - 1934

BT - STOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing

A2 - Mohar, Bojan

A2 - Shinkar, Igor

A2 - O�Donnell, Ryan

PB - Association for Computing Machinery

T2 - 56th Annual ACM Symposium on Theory of Computing, STOC 2024

Y2 - 24 June 2024 through 28 June 2024

ER -