초희박 무작위 그래프에서 독립 집합에 대한 제곱합 하한

우리는 모든 D와 충분히 큰 상수 d에 대해 G G (n, d/n) 선택에 대한 높은 확률로, - 무작위 그래프 분포에서, 표준 정도 2D 제곱합 완화가 G에서 가장 큰 독립 집합의 크기가 o(nd D⁴)임을 인증하는 데 실패함을 증명합니다. 특히, 정도 D 제곱합 강화는 전통적인 세타 SDP 완화의 전체 갭을 최대 O(D⁴) 요인만큼 줄일 수 있습니다. 이는 초희박 무작위 그래프에 대한 >4-정도 제곱합(SoS) 완화의 첫 번째 하한입니다(즉, 평균 정도가 절대 상수인 경우). 이러한 초희박 그래프는 이전 방법의 알려진 장벽이었으며 주요 열린 방향으로 명시적으로 식별되었습니다(예: ~deshpande2019threshold, kothari2021stressfree). 실제로 초희박 무작위 그래프에 대한 SoS 하한의 유일한 다른 예는 Max-Cut에 대한 4-정도 하한이었습니다. 우리의 주요 기술 결과는 그래프 행렬에 대한 스펙트럼 노름 추정치를 얻기 위한 새로운 방법입니다(G (n, d/n)에서 저차수 행렬 값 다항식의 클래스)로, 절대 상수 요인 내에서 정확합니다. 이전의 모든 작업은 o(n)-정도 무작위 그래프에 대한 하한을 무의미하게 만드는 log n 요인을 잃습니다. 우리는 이러한 새로운 하한을 pseudo-calibration에 의해 구축된 하한 목격자를 분석하기 위한 기계의 여러 업그레이드와 결합하여 분석에서 결과를 무의미하게 만들 수 있는 (1)-요인을 잃지 않도록 합니다. 다른 SoS 하한 외에도, 우리는 그래프 행렬에 대한 스펙트럼 노름 추정치를 설정하기 위한 우리의 방법이 평균 사례 입력에 대한 수치 알고리즘 분석에 유용할 것이라고 믿습니다.