يقدم الباحثون خوارزمية في وقت متعدد الحدود للاستعادة الدقيقة في مشكلة مطابقة بروكستس عالية الأبعاد، حيث يتم محاذاة مجموعتين من المتجهات الغاوسية عبر تبديل ودوران غير معروفين. تحسب الطريقة عدداً مرجحاً للأشجار الواسعة لتحقيق هذه المحاذاة.
- تنجح الخوارزمية باحتمال عالٍ عندما يكون البعد $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}$ ضروري لأي خوارزمية لعد الأشجار.
يعالج هذا العمل النظام عالي الأبعاد الذي كان غير مستكشف سابقاً، حيث كانت الضمانات السابقة تتطلب ارتباطاً شبه مثالي.