TL;DR

  • 다항식 크기 정수 입력에서 3SUM을 O(n^1.9992) 시간에, 정수 가중치가 다항식 범위인 방향 그래프의 APSP를 O(n^2.9995) 시간에 결정적으로 푸는 알고리즘임.
  • 결과는 교과서 알고리즘보다 처음으로 다항식 수준의 개선을 제공하며, 3SUM 가설과 APSP 가설을 반박함.
  • 핵심은 얇은 행렬 곱의 일부 항목만 계산하는 알고리즘으로, D ≤ N^(1/18)일 때 지정된 최대 N²/√D개 항목을 O(N²/D^0.063) 연산으로 계산함.
  • 이 알고리즘은 희소 비대칭 삼분 그래프의 모든 간선 희소 삼각형 문제를 진정한 준이차 시간에 풀며, 정확 삼각형 가설, 영 가중치 k-클리크 가설 및 세 가지 직사각형 힌트 온라인 행렬-벡터 추측도 반박함.
  • 단일 행렬 항목 질의에 답하는 자료 구조 버전과 여러 문제의 다항식 속도 향상도 제시함.

논문 정보

  • Josh Alman과 Virginia Vassilevska Williams의 논문 제목은 “희소 비대칭 그래프의 삼각형을 통한 진정한 준이차 시간 3SUM 및 진정한 준삼차 시간 APSP”임.
  • arXiv:2610.06783, 분야는 자료 구조 및 알고리즘(cs.DS), 계산 복잡도(cs.CC)이며, 제출일은 2026년 10월 5일임.
  • 논문 링크: https://doi.org/10.48550/arXiv.2610.06783

3SUM과 APSP의 시간 개선

  • 다항식 크기 정수 n개에 대한 3SUM을 결정적으로 O(n^1.9992) 시간에 해결함.
  • 다항식 범위의 정수 가중치를 가진 방향 n개 정점 그래프의 모든 쌍 최단 경로(APSP)를 O(n^2.9995) 시간에 해결함.
  • 두 알고리즘 모두 교과서 알고리즘 대비 최초의 다항식 수준 개선이며, 기존 3SUM 가설과 APSP 가설을 반박함.
  • 알려진 환원으로 실수값 버전의 3SUM 및 APSP 가설, 정확 삼각형(Exact Triangle) 가설, 영 가중치 k-클리크(Zero-Weight k-Clique) 가설, van den Brand, Nanongkai, Saranurak의 세 가지 직사각형 힌트 온라인 행렬-벡터 추측도 반박하며, 여러 다른 문제의 다항식 속도 향상을 제공함.

얇은 행렬 곱 알고리즘

  • 모든 결과의 기반은 지정된 위치의 행렬 곱 항목만 계산하는 단일 알고리즘임.
  • X는 N×D 정수 행렬, Y는 D×N 정수 행렬이며, D ≤ N^(1/18)임. 최대 N²/√D개 위치로 이루어진 집합 W에 대해 (XY)[I,J], 즉 (I,J) ∈ W인 항목을 O(N²/D^0.063) 연산으로 계산함.
  • 이 연산량은 전체 XY 행렬을 기록하거나 N²/√D개의 내적을 하나씩 계산하는 데 필요한 시간보다 다항식 수준으로 적음.
  • Schönhage의 10회 곱셈 항등식을 이용하는 Coppersmith 직사각형 행렬 곱셈 알고리즘의 변형을 설계하고, W에 속한 항목 계산에 필요한 연산만 수행하도록 수정해 연산 수가 적음을 보임.

희소 비대칭 그래프와 응용

  • 그래프 알고리즘으로 해석하면, 정점이 각각 n, n, n^ε개인 희소 비대칭 삼분 그래프에서 모든 간선 희소 삼각형(All-Edges Sparse Triangle) 문제를 ε < 0.12일 때 진정한 준이차 시간에 해결함.
  • 알려진 환원에 따라 정확 삼각형 문제가 이 문제로 환원되며, 정확 삼각형을 거쳐 3SUM과 APSP도 이 문제로 환원됨.
  • 질의 대상 항목을 미리 알 필요 없이 XY의 단일 항목을 묻는 질의에 답하는 자료 구조 버전도 제시함.