밀집 k-부분 그래프에 대한 합 제곱 하한

그래프와 정수 k가 주어지면, 밀집 k-부분 그래프는 k개의 정점에서 최대 엣지 수를 가진 부분 그래프를 찾는 알고리즘적 작업입니다. 이는 수십 년 동안 집중적으로 연구된 근본적인 문제로, 다양한 분야에 걸쳐 응용됩니다. 최첨단 알고리즘은 Bhaskara et al. STOC '10에 의해 O(n1/4 + )-인자 근사치입니다. 더욱이, 이른바 로그 밀도 프레임워크는 이것이 최적임을 예측하며, 즉 효율적인 알고리즘이 O(n1/4 − )-인자 근사치를 달성하는 것은 불가능하다는 것입니다. 평균적인 경우, 밀집 k-부분 그래프는 통계적-계산적 격차를 보일 것이라 추정되는 전형적인 소음 추론 작업입니다.