باسين مانورانجسي: إثبات ما لا تستطيع الحواسيب فعله

في يوليو 2011، استضافت مدينة باتايا التايلاندية النسخة الثالثة والعشرين من الأولمبياد الدولي للمعلوماتية (IOI)، وهي المرة الأولى التي تستضيف فيها تايلاند هذا الحدث، وافتتح رئيس الوزراء أبهيسيت فيجاجيفا (Abhisit Vejjajiva) الألعاب في واحدة من آخر مهامه الرسمية. ومن بين الفريق المضيف، كان هناك طالب من كلية بانكوك المسيحية (Bangkok Christian College) أنهى المنافسة في المركز الرابع عشر من بين 303 متسابقين برصيد 524 نقطة، وحصد ميدالية ذهبية ثانية على التوالي. أخبر الصحفيين أنه مسرور بالمركز الرابع عشر، وأن الـ 524 نقطة كانت أكثر مما كان يتوقع، وأعرب عن أمله في أن يؤدي استضافة الأولمبياد إلى إثارة المزيد من الاهتمام بالحواسيب بين الشباب التايلاندي. بعد خمسة عشر عاماً، أصبح باسين مانورانجسي (Pasin Manurangsi) أحد الباحثين الذين تتمثل وظيفتهم في إخبار بقية مجال علوم الحاسوب بالمشكلات الميؤوس منها.

قوس الأولمبياد

يقرأ سجل منافسات مانورانجسي وكأنه تجربة مضبوطة للتحسين. في أولمبياد المعلوماتية الدولي لعام 2009 في بلغاريا، سجل 516 نقطة واحتل المركز 67 من أصل 301، محققاً الفضية. وفي عام 2010، في كندا، سجل 704 نقاط واحتل المركز 12 من أصل 297، محققاً الذهبية. وفي عام 2011، على أرض الوطن، فاز بالذهبية مرة أخرى بينما فازت تايلاند بالميدالية الذهبية للفريق في المنافسة التي كانت تستضيفها للمرة الأولى. ثلاث مشاركات، ميداليتان ذهبيتان وفضية، وقفزة بخمسة وخمسين مركزاً في التصنيف العالمي بين محاولته الأولى والثانية: مسار شخص تعامل مع الخسارة كوثيقة مواصفات بدلاً من حكم نهائي.

معهد ماساتشوستس للتكنولوجيا ومعضلة الاقتراب الكافي

حصل مانورانجسي على درجتي البكالوريوس والماجستير من معهد ماساتشوستس للتكنولوجيا (MIT)، حيث كانت أطروحة الماجستير الخاصة به، تحت إشراف دانا موشكوفيتز (Dana Moshkovitz)، تتعلق بخوارزميات التقريب لألعاب الإسقاط (projection games). حدد اختيار ذلك الموضوع اتجاه كل ما تلاه. التقريب هو الحل الوسط البراغماتي لهذا التخصص: عندما لا يمكن حل مشكلة بدقة في وقت معقول، فإنك تقبل بإجابة مضمونة لتكون ضمن عامل معين من الإجابة المثالية. السؤال المثير للاهتمام، والذي عاد إليه مانورانجسي مراراً، هو إلى أي مدى يمكن أن يصل ذلك الضمان قبل أن يصطدم بجدار رياضي.

بيركلي: البلد الواقع بين P و NP

أكمل الدكتوراه في جامعة كاليفورنيا، بيركلي (University of California, Berkeley) في مايو 2019، تحت إشراف مشترك من لوكا تريفيسان (Luca Trevisan) وبراساد راغافيندرا (Prasad Raghavendra)، مع وجود نيخيل سريفاستافا (Nikhil Srivastava) في اللجنة. كان عنوان الأطروحة التقريب والصلابة: ما وراء P و NP (Approximation and Hardness: Beyond P and NP)، وطموحها واضح في العنوان. تصنف نظرية التعقيد الكلاسيكية المشكلات إلى تلك القابلة للحل (P) وتلك الصعبة (NP-complete). بحثت أطروحة مانورانجسي عمداً في التضاريس التي لا تغطيها هذه الفئات: المشكلات التي ليست في P ولا تُعرف بأنها NP-hard، مثل مشكلات المجموعات المسيطرة (k-dominating set)، وk-clique، وk-biclique، وشبكات شتاينر الموجهة (directed Steiner network)، ومشكلات الشبكات (lattice problems)، والأكثر مخالفة للبديهة، المشكلات التي تقع بشكل مريح داخل P، مثل الزوج الأقرب (closest pair) والحد الأقصى للناتج الداخلي (maximum inner product)، والتي تقاوم التقريب السريع على أي حال. يدعي الملخص أن العمل يحل سؤالين مفتوحين منذ فترة طويلة في التعقيد البارامتري (parameterized complexity) ويقدم أفضل عوامل عدم القابلية للتقريب المعروفة للعديد من المشكلات. إنها أطروحة حول رسم الحدود، لا عبورها.

جدار k-مخطط فرعي الأكثر كثافة

النتيجة الوحيدة التي صنعت اسمه تتعلق بـ "k-مخطط فرعي الأكثر كثافة" (Densest k-Subgraph): بالنظر إلى شبكة، اعثر على k عقدة مرتبطة بأكثر الروابط كثافة. أثبت مانورانجسي أنه بموجب فرضية الوقت الأسي (exponential time hypothesis)، لا يمكن لأي خوارزمية ذات وقت حدودي تحقيق نسبة تقريب أفضل من n أس (1/(log log n)) مضروباً في ثابت، وأنه بموجب فرضية Gap-ETH الأقوى، يضيق الحاجز إلى n^f(n) لأي دالة f تتجه إلى الصفر، وهو ما يقترب جداً من الصلابة الحدودية. ومن الأهمية بمكان أن البناء يتمتع بما يسميه المجال بالكمال التام: فهو يميز المخططات التي تحتوي حقاً على k-clique عن المخططات التي يكون فيها كل k-مخطط فرعي متناثراً. فازت الورقة البحثية بجائزة داني لوين لأفضل ورقة طلابية في مؤتمر STOC 2017، وهو المؤتمر النظري الرائد في هذا التخصص.

جوجل، الخصوصية والقسمة العادلة

منذ يوليو 2019، كان مانورانجسي باحثاً علمياً في جوجل للأبحاث (Google Research)، حيث تشمل مجالاته المدرجة الخوارزميات والنظرية، وذكاء الآلة، ومكافحة الإساءة، وقد جمع أكثر من مائة منشور. انتقل مركز الثقل من عدم القابلية للتقريب البحتة نحو الخصوصية التفاضلية (differential privacy)، ونظرية التعلم، والاختيار الاجتماعي الحسابي — القسمة العادلة، وتنصيف الإجماع، وتجميع الرتب الخاص، وتوليد البيانات الاصطناعية. تظهر إحدى النتائج الحديثة أن تنصيف الإجماع بما يصل إلى O(√(n log n)) من السلع موجود دائماً لـ n من الوكلاء ذوي المنفعة الرتيبة، مما يحسن حداً سابقاً. استمرت الجوائز في الوصول: أفضل ورقة في WAOA 2021، وأفضل ورقة طلابية في ALT 2021، وأفضل ورقة وتنويه لأفضل ورقة في FORC 2026، بالإضافة إلى تقدير لجنة البرنامج المتميزة في IJCAI في عامي 2021 و2023 وحالة المراجع الأعلى في NeurIPS 2023.

رحلة العودة

منذ عام 2022، أصبح جزءاً من فرق التدريب لأولمبياد المعلوماتية والرياضيات في تايلاند، وشغل منصب عضو وفد ضيف لتايلاند في أولمبياد المعلوماتية الدولي 2024. ومنذ عام 2023، عمل أيضاً كعضو هيئة تدريس مساعد في جامعة CMKL، حيث يدرس الخوارزميات وهياكل البيانات وخوارزميات الحفاظ على الخصوصية. المسار الذي أنتجه هو مسار يساعد الآن في إدارته.

لماذا يُسمى باسين عبقرياً

الجودة المعرفية المعنية هنا محددة بشكل غير عادي، وليست السرعة الخام. يكافئ نجاح الأولمبياد حل المشكلات السريع والدقيق تحت ضغط الوقت؛ بينما يكافئ البحث في صلابة التقريب العكس تماماً — الصبر لبناء اختزال متقن يثبت أن فئة كاملة من الخوارزميات محكوم عليها بالفشل. مانورانجسي نادر في كونه فعل كلاهما على مستوى عالٍ، وأطروحة بيركلي هي الدليل: فهي تضع أرضية يتجنبها معظم الباحثين لأن النتائج السلبية أصعب في النشر وأصعب في الصواب. أي زلة منطقية واحدة في الاختزال تبطل كل شيء.

الحالة المضادة الصادقة كبيرة. لا شيء في السجل الموثق — صفحته الرئيسية، ملف تعريف جوجل للأبحاث، أطروحته، أو التغطية الصحفية التايلاندية المعاصرة — يستخدم كلمة "عبقري" عنه. جوائزه هي جوائز أقران من لجان المؤتمرات، التي تعترف بأفضل ورقة في الغرفة، وليس بعقل للعصور. نظرية علوم الحاسوب أيضاً تعاونية بلا هوادة؛ أوراقه المائة وأكثر هي نتاج تأليف مشترك، وندوات، ومجموعة بيركلي بقيادة اثنين من أقوى منظري التعقيد في المجال. سجله في أولمبياد المعلوماتية الدولي، رغم كونه ممتازاً، يتضمن إنهاءً في المركز 67. ما يمكن قوله دون تضخم هو أضيق وأكثر إثارة للاهتمام: إنه محترف من الدرجة الأولى في واحدة من أكثر زوايا الرياضيات تطلباً من الناحية الفنية، وقد أنهت نتيجته المحددة سؤالاً كان مفتوحاً لسنوات. هذا ليس هو نفسه العبقرية، ولم يزعم هو أبداً أنها كذلك.

التوقعات

مسيرة مانورانجسي المهنية لها شكل غير عادي لمنظر: جاءت براهين الاستحالة أولاً، والعمل التطبيقي على الخصوصية ثانياً. يشير الانتقال إلى الخصوصية التفاضلية والقسمة العادلة إلى شخص، بعد أن حدد مكان الجدران، يفضل الآن البناء داخلها. قد يثبت تدريب أولمبياد تايلاند أنه الإرث الأكثر ديمومة — بلد استضاف أولمبياد المعلوماتية الدولي مرة واحدة، وينمي الآن الأشخاص الذين يفوزون به.