Key points are not available for this paper at this time.
이분법, 그래프 색칠, 클리크와 같은 문제는 일반적으로 최악의 경우 어렵다고 여겨진다. 그러나 입력 데이터가 허용 가능한 솔루션을 포함하는 그래프의 분포에서 무작위로 추출되면 해결할 수 있다. 이 논문에서는 간단한 스펙트럼 알고리즘이 위의 세 가지 문제를 평균 경우에서 해결할 수 있으며, 에지 밀도를 기반으로 그래프를 분할하는 더 일반적인 문제도 해결할 수 있음을 보여준다. 거의 모든 경우에 우리의 접근 방식은 이전 매개변수를 충족하거나 초과하면서 상당한 일반성을 도입한다. 우리는 이러한 문제의 모든 경우에서 예상 인접 행렬이 솔루션의 구조가 명백한 저차 행렬이라는 관찰을 사용하여 스펙트럼 기술을 적용한다.
Frank McSherry (Mon,)는 이 질문을 연구했다.