연구자들은 미지의 순열과 회전을 통해 두 집합의 가우스 벡터를 정렬하는 고차원 프로크레스 정렬 문제에서 정확한 복원을 위한 다항식 시간 알고리즘을 제시했습니다. 이 방법은 넓은 나무의 개수를 계산하여 이 정렬을 달성합니다.
- 알고리즘은 차원 $d \ge \mathrm{polylog}(n)$ 및 상관관계 제곱 $\rho^2 > \sqrt{\alpha}$ (여기서 $\alpha \approx 0.338$은 오테르의 나무 세기 상수)일 때 높은 확률로 성공합니다.
- 개선된 정보이론적 보장은 $\rho^2 \gtrsim \max\{\log n/d, \sqrt{\log n/n}\}$일 때 정확한 복원이 가능함을 보여줍니다.
- 저차 다항식 이점 계산은 임의의 나무 세기 알고리즘에 대해 조건 $\rho^2 > \sqrt{\alpha}$가 필요함을 시사합니다.
이 연구는 이전 보장이 거의 완벽한 상관관계를 요구했던Previously 미개척된 고차원 영역을 다루고 있습니다.