研究者らは、2組のガウスベクトルが未知の順列と回転によって整列される高次元プロクレスティングマッチング問題における正確な復元のための多項式時間アルゴリズムを発表した。この手法は、広大な木の数え上げを用いてこの整列を実現する。

  • アルゴリズムは、次元 $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}$ が必要であることを示唆している。

この研究は、以前の保証がほぼ完全な相関を必要としていた、これまで未開拓の高次元領域に取り組んでいる。