تقدير كثافة الطيف الأسرع وتقليل الأبعاد في المعايير النووية

نعتبر مشكلة تقدير كثافة الطيف لمصفوفة الجوار المعنوية لمخطط غير موجه يحتوي على n عقدة. نقدم خوارزمية عشوائية التي، مع O (n^-2) استفسارات إلى Oracle من الدرجة والجيران وفي O (n^-3) وقت، تُقدر الطيف بدقة تصل إلى مقياس Wasserstein-1. يحسن هذا من الأساليب السابقة الرائدة، بما في ذلك خوارزمية من O (n^-7) من Braverman وآخرين، STOC 2022 ومن أجل الأوقات الصغيرة بما فيه الكفاية، خوارزمية من 2^O (^{-1) } من Cohen-Steiner وآخرين، KDD 2018. لتحقيق هذه النتيجة، نقدم مفهوم جديد لتقليل كثافة المخططات، والذي نطلق عليه اسم تقليل الكثافة النووية. نقدم خوارزمية تحسب O (n^-2) -محللات نووية بتعقيد O (n^-2) -استفسارات و O (n^-2) -وقت. نظهر أن هذا الحد مثالي في كل من كفاءة الكثافة وتعقيد الاستفسار، ونفصل نتائجنا عن المفهوم المرتبط بتقليل الطيف الإضافي. من اهتمامات مستقلة، نظهر أن طريقتنا في التقليل أيضًا تُنتج أول خوارزمية حتمية لتقدير كثافة الطيف التي تتوسع خطيًا مع n (تحت الخطية في حجم تمثيل المخطط).