पासीन मानुरंगसी: कंप्यूटर क्या नहीं कर सकते, यह सिद्ध करना

जुलाई 2011 में, थाईलैंड के रिसॉर्ट शहर पटाया ने 23वें अंतरराष्ट्रीय सूचना विज्ञान ओलंपियाड (IOI) का आयोजन किया, जो पहली बार था जब थाईलैंड ने इस आयोजन की मेजबानी की थी, और प्रधान मंत्री अमिषित वेज्जजीवा (Abhisit Vejjajiva) ने अपने अंतिम आधिकारिक कृत्यों में से एक के रूप में खेलों का उद्घाटन किया। घरेलू टीम के बीच बैंकॉक क्रिश्चियन कॉलेज (Bangkok Christian College) का एक छात्र था, जिसने 524 अंकों के साथ 303 प्रतियोगियों में 14वां स्थान हासिल किया और लगातार दूसरा स्वर्ण पदक जीता। उन्होंने पत्रकारों को बताया कि वे 14वें स्थान से प्रसन्न थे, कि 524 अंक उनकी उम्मीद से अधिक थे, और उन्होंने आशा व्यक्त की कि ओलंपियाड की मेजबानी से थाई युवाओं में कंप्यूटर के प्रति अधिक रुचि पैदा होगी। पंद्रह साल बाद, पासीन मानुरंगसी (Pasin Manurangsi) उन शोधकर्ताओं में से एक हैं जिनका काम बाकी कंप्यूटर विज्ञान को यह बताना है कि कौन सी समस्याएं निराशाजनक हैं।

ओलंपियाड का सफर

मानुरंगसी का प्रतिस्पर्धी रिकॉर्ड सुधार के एक नियंत्रित प्रयोग की तरह पढ़ा जाता है। बुल्गारिया में 2009 के IOI में उन्होंने 516 अंक बनाए और 301 में से 67वें स्थान पर रहे, जहाँ उन्हें रजत पदक मिला। 2010 में, कनाडा में, उन्होंने 704 अंक बनाए और 297 में से 12वें स्थान पर रहकर स्वर्ण पदक हासिल किया। 2011 में, अपनी घरेलू धरती पर, उन्होंने फिर से स्वर्ण पदक जीता क्योंकि थाईलैंड ने उस प्रतियोगिता में टीम स्वर्ण पदक जीता जिसकी उसने पहली बार मेजबानी की थी। तीन बार की उपस्थिति, दो स्वर्ण और एक रजत, और उनके पहले और दूसरे प्रयास के बीच विश्व रैंकिंग में पचपन स्थानों की छलांग: यह उस व्यक्ति का प्रक्षेपवक्र है जिसने हार को फैसले के बजाय एक विनिर्देश दस्तावेज के रूप में लिया।

एमआईटी, और पर्याप्त करीब आने की समस्या

मानुरंगसी ने अपनी स्नातक और मास्टर डिग्री मैसाचुसेट्स इंस्टीट्यूट ऑफ टेक्नोलॉजी (MIT) से प्राप्त की, जहाँ उनका मास्टर का काम, दाना मोशकोवित्ज़ (Dana Moshkovitz) की देखरेख में, प्रोजेक्शन गेम्स के लिए सन्निकटन एल्गोरिदम (approximation algorithms) से संबंधित था। उस विषय के चयन ने उसके बाद की हर चीज की दिशा निर्धारित कर दी। सन्निकटन इस अनुशासन का व्यावहारिक समझौता है: जब किसी समस्या को उचित समय में सटीक रूप से हल नहीं किया जा सकता है, तो आप एक ऐसे उत्तर के लिए समझौता करते हैं जो सर्वोत्तम के कुछ कारक के भीतर होने की गारंटी देता है। दिलचस्प सवाल, और जिस पर मानुरंगसी बार-बार लौटते रहे, यह है कि गणितीय दीवार से टकराने से पहले वह गारंटी कितनी अच्छी हो सकती है।

बर्कले: P और NP के बीच का देश

उन्होंने मई 2019 में कैलिफोर्निया विश्वविद्यालय, बर्कले (University of California, Berkeley) से अपनी डॉक्टरेट पूरी की, जिसे लुका ट्रेविसन (Luca Trevisan) और प्रसाद राघवेन्द्र (Prasad Raghavendra) ने सह-पर्यवेक्षित किया, और निखिल श्रीवास्तव (Nikhil Srivastava) समिति में थे। थीसिस का शीर्षक सन्निकटन और कठोरता: P और NP से परे (Approximation and Hardness: Beyond P and NP) था, और इसका उद्देश्य शीर्षक में दिखाई देता है। शास्त्रीय जटिलता सिद्धांत समस्याओं को सुलझाने योग्य (P) और कुख्यात कठिन (NP-पूर्ण) में छाँटता है। मानुरंगसी के शोध प्रबंध ने जानबूझकर उन इलाकों में शिकार किया जिन्हें वे श्रेणियां कवर नहीं करती हैं: वे समस्याएं जो न तो P में हैं और न ही NP-कठिन के रूप में जानी जाती हैं, जैसे कि k-डोमिनेटिंग सेट (k-dominating set), k-क्लीक (k-clique), k-बिक्लीक (k-biclique), निर्देशित स्टेनर नेटवर्क (directed Steiner network) और लैटिस समस्याएं, और - सबसे अतार्किक रूप से - वे समस्याएं जो P के भीतर आराम से बैठती हैं, जैसे कि क्लोजेस्ट पेयर (closest pair) और अधिकतम आंतरिक उत्पाद (maximum inner product), लेकिन जो फिर भी तेजी से सन्निकटन का विरोध करती हैं। सार दावा करता है कि यह काम पैरामीटराइज्ड जटिलता (parameterized complexity) में दो लंबे समय से खुले सवालों को हल करता है और कई समस्याओं के लिए सर्वोत्तम ज्ञात गैर-सन्निकटन कारक प्रदान करता है। यह सीमाओं को पार करने के बारे में नहीं, बल्कि उन्हें खींचने के बारे में एक थीसिस है।

सबसे सघन k-सबग्राफ दीवार

जिस एकल परिणाम ने उनका नाम बनाया वह 'सबसे सघन k-सबग्राफ' (Densest k-Subgraph) से संबंधित है: एक नेटवर्क को देखते हुए, सबसे कसकर कनेक्शन वाले k नोड्स खोजें। मानुरंगसी ने साबित किया कि घातीय समय परिकल्पना (exponential time hypothesis) के तहत, कोई भी बहुपद-समय एल्गोरिदम n की 1/(log log n) की शक्ति से बेहतर सन्निकटन अनुपात प्राप्त नहीं कर सकता है - और यह कि मजबूत Gap-ETH धारणा के तहत बाधा शून्य की ओर जाने वाले किसी भी फ़ंक्शन f के लिए n^f(n) तक तंग हो जाती है, जो लगभग बहुपद कठोरता है। महत्वपूर्ण रूप से निर्माण में वह है जिसे क्षेत्र 'पूर्ण पूर्णता' (perfect completeness) कहता है: यह उन ग्राफ़ों को अलग करता है जिनमें वास्तव में k-क्लीक होता है उन ग्राफ़ों से जहाँ हर k-सबग्राफ विरल होता है। पेपर ने STOC 2017 में डैनी लेविन बेस्ट स्टूडेंट पेपर अवार्ड (Danny Lewin Best Student Paper Award) जीता, जो अनुशासन का प्रमुख सिद्धांत सम्मेलन है।

गूगल, गोपनीयता और निष्पक्ष विभाजन

जुलाई 2019 से मानुरंगसी गूगल रिसर्च (Google Research) में एक शोध वैज्ञानिक रहे हैं, जहाँ उनके सूचीबद्ध क्षेत्र एल्गोरिदम और सिद्धांत, मशीन इंटेलिजेंस और एंटी-एब्यूज हैं, और जहाँ उन्होंने सौ से अधिक प्रकाशन जमा किए हैं। गुरुत्वाकर्षण का केंद्र शुद्ध गैर-सन्निकटन से अंतर गोपनीयता (differential privacy), सीखने के सिद्धांत और कम्प्यूटेशनल सामाजिक विकल्प - निष्पक्ष विभाजन, सहमति विभाजन, निजी रैंक एकत्रीकरण, सिंथेटिक डेटा पीढ़ी की ओर स्थानांतरित हो गया है। एक हालिया परिणाम दिखाता है कि मोनोटोन उपयोगिताओं वाले n एजेंटों के लिए O(√(n log n)) तक का सहमति विभाजन हमेशा मौजूद होता है, जो पिछले सीमा में सुधार करता है। पुरस्कार आते रहे हैं: WAOA 2021 में बेस्ट पेपर, ALT 2021 में बेस्ट स्टूडेंट पेपर, FORC 2026 में एक बेस्ट पेपर और बेस्ट पेपर ऑनरेबल मेंशन, साथ ही 2021 और 2023 में IJCAI में प्रतिष्ठित कार्यक्रम समिति की मान्यता और NeurIPS 2023 में शीर्ष-समीक्षक का दर्जा।

वापसी की यात्रा

2022 से वे थाईलैंड के सूचना विज्ञान ओलंपियाड और इसके गणितीय ओलंपियाड शिविरों के लिए कोचिंग टीमों का हिस्सा रहे हैं, और उन्होंने 2024 IOI में थाईलैंड के लिए अतिथि प्रतिनिधिमंडल के सदस्य के रूप में कार्य किया। 2023 से वे CMKL विश्वविद्यालय में सहायक संकाय भी रहे हैं, जो एल्गोरिदम, डेटा संरचनाएं और गोपनीयता-संरक्षण एल्गोरिदम पढ़ा रहे हैं। जिस पाइपलाइन ने उन्हें बनाया, वह अब वे चलाने में मदद करते हैं।

पासीन को जीनियस क्यों कहा जाता है

यहाँ चर्चा का संज्ञानात्मक गुण असामान्य रूप से विशिष्ट है, और यह कच्ची गति नहीं है। ओलंपियाड की सफलता घड़ी के तहत तेज़, सटीक समस्या-समाधान को पुरस्कृत करती है; सन्निकटन की कठोरता बिल्कुल विपरीत को पुरस्कृत करती है - एक विस्तृत कमी का निर्माण करने का धैर्य जो यह साबित करता है कि एल्गोरिदम का पूरा वर्ग बर्बाद है। मानुरंगसी उच्च स्तर पर दोनों करने वाले दुर्लभ व्यक्ति हैं, और बर्कले थीसिस इसका सबूत है: यह उस क्षेत्र को बाहर निकालता है जिसे अधिकांश शोधकर्ता ठीक इसलिए छोड़ देते हैं क्योंकि नकारात्मक परिणाम प्रकाशित करना कठिन होता है और सही प्राप्त करना कठिन होता है। कमी में एक भी तार्किक चूक सब कुछ अमान्य कर देती है।

ईमानदार काउंटर-केस काफी है। स्रोत रिकॉर्ड में कुछ भी नहीं - उनका अपना होमपेज, गूगल रिसर्च प्रोफ़ाइल, शोध प्रबंध, या समकालीन थाई प्रेस कवरेज - उनके बारे में 'जीनियस' शब्द का उपयोग करता है। उनके सम्मान सम्मेलन समितियों से सहकर्मी पुरस्कार हैं, जो कमरे में सबसे अच्छे पेपर को पहचानते हैं, न कि युगों के लिए एक दिमाग को। सैद्धांतिक कंप्यूटर विज्ञान भी लगातार सहयोगात्मक है; उनके सौ से अधिक पेपर सह-लेखन, सेमिनार और क्षेत्र के दो सबसे मजबूत जटिलता सिद्धांतकारों के नेतृत्व वाले बर्कले समूह का उत्पाद हैं। उनका IOI रिकॉर्ड, हालांकि उत्कृष्ट है, 67वें स्थान की फिनिश शामिल है। जो बिना मुद्रास्फीति के कहा जा सकता है वह संकरा और अधिक दिलचस्प है: वे गणित के सबसे तकनीकी रूप से मांग वाले कोनों में से एक में प्रथम श्रेणी के पेशेवर हैं, और उनके परिभाषित परिणाम ने एक ऐसा सवाल बंद कर दिया जो वर्षों से खुला था। यह जीनियस होने जैसा नहीं है, और उन्होंने कभी ऐसा दावा नहीं किया है।

आउटलुक

मानुरंगसी के करियर में एक सिद्धांतवादी के लिए असामान्य आकार है: असंभवता के प्रमाण पहले आए, व्यावहारिक गोपनीयता का काम दूसरे नंबर पर। अंतर गोपनीयता और निष्पक्ष विभाजन की ओर कदम उस व्यक्ति का सुझाव देता है जिसने यह स्थापित कर लिया है कि दीवारें कहाँ हैं, अब उनके अंदर निर्माण करना पसंद करेंगे। थाई ओलंपियाड कोचिंग सबसे स्थायी विरासत साबित हो सकती है - एक ऐसा देश जिसने एक बार IOI की मेजबानी की, और अब उन लोगों को विकसित करता है जो इसे जीतते हैं।