2023 का ACM Turing Award प्रोफेसर Avi Wigderson को प्रदान

• सैद्धांतिक कंप्यूटर साइंस, कंप्यूटिंग क्षेत्र की गणितीय नींव से संबंधित है। यह ऐसे सवाल उठाता है जैसे, "क्या इस समस्या को कंप्यूटिंग के जरिए हल किया जा सकता है?", "अगर इस समस्या को कंप्यूटिंग से हल किया जा सकता है, तो इसमें कितना समय और कितने संसाधन लगेंगे?"। यह कुशल algorithms डिज़ाइन करने के तरीकों की भी पड़ताल करता है। हमारे जीवन को प्रभावित करने वाली हर कंप्यूटिंग तकनीक algorithms की वजह से संभव है। शक्तिशाली और कुशल algorithms के सिद्धांतों को समझना न केवल कंप्यूटर साइंस बल्कि प्रकृति के नियमों की समझ को भी गहरा करता है। सैद्धांतिक कंप्यूटर साइंस को एक ऐसे क्षेत्र के रूप में जाना जाता है जो रोचक बौद्धिक चुनौतियाँ प्रस्तुत करता है, और अक्सर कंप्यूटिंग के व्यावहारिक अनुप्रयोगों के सीधे सुधार से जुड़ा नहीं दिखता, लेकिन इस क्षेत्र के शोध-नवाचार cryptography, computational biology, network design, machine learning, quantum computing सहित लगभग हर क्षेत्र में प्रगति का कारण बनते हैं.

• मूल रूप से कंप्यूटर deterministic systems होते हैं। किसी algorithm के निर्देशों के सेट को किसी विशेष input पर लागू करने पर computation uniquely तय होता है, और विशेष रूप से output भी तय होता है। यानी deterministic algorithms पूर्वानुमानित पैटर्न का पालन करते हैं। इसके विपरीत, randomness में स्पष्ट रूप से परिभाषित पैटर्न या घटनाओं/परिणामों की पूर्वानुमेयता का अभाव होता है। चूँकि जिस दुनिया में हम रहते हैं वह random घटनाओं (जैसे weather systems, biological/quantum phenomena आदि) से भरी हुई लगती है, इसलिए कंप्यूटर वैज्ञानिकों ने algorithms को इस तरह सशक्त किया है कि वे computation प्रक्रिया में random choices कर सकें, ताकि उनकी efficiency बढ़ाई जा सके। वास्तव में, कई ऐसी समस्याएँ जिनके लिए कुशल deterministic algorithms ज्ञात नहीं हैं, probabilistic algorithms द्वारा कुशलता से हल की गई हैं (हालाँकि उनमें थोड़ी-सी error probability होती है, जिसे प्रभावी रूप से घटाया जा सकता है)। लेकिन क्या randomness वास्तव में अनिवार्य है, या इसे हटाया जा सकता है? probabilistic algorithms की सफलता के लिए randomness की गुणवत्ता कैसी होनी चाहिए?

• डॉ. Avi Wigderson ने 40 वर्षों तक सैद्धांतिक कंप्यूटर साइंस के शोध का नेतृत्व किया है और कंप्यूटिंग में randomness तथा pseudorandomness की भूमिका की समझ में बुनियादी योगदान दिया है। कंप्यूटर वैज्ञानिकों ने randomness और computational hardness (ऐसी स्वाभाविक समस्याओं की पहचान, जिनके लिए कुशल algorithms नहीं हैं) के बीच उल्लेखनीय संबंध पाए हैं। डॉ. Wigderson ने अपने सहयोगियों के साथ randomness के बदले hardness के tradeoff पर अत्यंत प्रभावशाली शोध-श्रृंखला की। उन्होंने मानक और व्यापक रूप से स्वीकृत computational assumptions के तहत यह सिद्ध किया कि सभी probabilistic polynomial time algorithms से randomness को कुशलता से हटाया जा सकता है (अर्थात उन्हें पूरी तरह deterministic बनाया जा सकता है)। दूसरे शब्दों में, randomness कुशल computation के लिए अनिवार्य नहीं है। इस शोध-श्रृंखला ने कंप्यूटिंग में randomness की भूमिका और उसके बारे में हमारी सोच, दोनों को बदल दिया.

डॉ. Wigderson के योगदान

• "Hardness vs. Randomness" (Noam Nisan के साथ सह-लेखन): इस पेपर ने, अन्य बातों के साथ, एक नए प्रकार का pseudorandom generator पेश किया और यह सिद्ध किया कि पहले से ज्ञात परिणामों की तुलना में कहीं अधिक कमजोर assumptions के तहत randomized algorithms का कुशल deterministic simulation संभव है.

• "BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs" (László Babai, Lance Fortnow, Noam Nisan के साथ सह-लेखन): इस पेपर ने "hardness amplification" का उपयोग कर यह दिखाया कि bounded-error probabilistic polynomial time(BPP) को अधिक कमजोर assumptions के तहत अनंत रूप से कई input lengths के लिए subexponential time में simulate किया जा सकता है.

• "P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma" (Russell Impagliazzo के साथ सह-लेखन): इस पेपर ने एक अधिक शक्तिशाली pseudorandom generator प्रस्तुत किया, जिसमें मूलतः सर्वोत्तम hardness vs randomness tradeoff था.

• randomness से जुड़े शोध से आगे बढ़कर भी, डॉ. Wigderson ने multi-prover interactive proofs, cryptography, circuit complexity जैसे सैद्धांतिक कंप्यूटर साइंस के कई अन्य क्षेत्रों में बौद्धिक नेतृत्व दिखाया है.

GN⁺ की राय

• गणितीय दृष्टि से randomness और computational complexity के बीच संबंध को सिद्ध करने वाला Wigderson का शोध, कंप्यूटर साइंस और गणित के संगम के लिहाज़ से बहुत महत्वपूर्ण है। खास तौर पर, यह सिद्ध करना कि randomness पर निर्भर कई algorithms वास्तव में deterministic रूप में भी समान तरीके से लागू किए जा सकते हैं, कंप्यूटर साइंस के लिए एक नए क्षितिज के खुलने जैसा माना जा सकता है.

• इसके अलावा efficiency और hardness के संबंध को गणितीय रूप से समझने का प्रयास भी सैद्धांतिक कंप्यूटर साइंस का एक महत्वपूर्ण शोध-विषय बनता दिखता है। यह विचार कि जितनी कठिन समस्या हो, उसके अनुपात में उतने ही अधिक कुशल algorithms के अस्तित्व की संभावना हो सकती है, एक सहज नहीं बल्कि गहरी अंतर्दृष्टि है.

• दूसरी ओर, प्रोफेसर Wigderson ने सैद्धांतिक कंप्यूटर साइंस के विकास के लिए गणित और कंप्यूटर साइंस के समन्वय पर ज़ोर दिया और अगली पीढ़ी के शोधकर्ताओं को तैयार करने में भी योगदान दिया। विशेष रूप से, गणित के Abel Prize और कंप्यूटर साइंस के Turing Award दोनों प्राप्त करने का उनका रिकॉर्ड सैद्धांतिक कंप्यूटर साइंस के महत्व को दर्शाने वाला एक प्रतीकात्मक उदाहरण कहा जा सकता है.

[GN⁺]

Hacker News राय

• Avi Wigderson को 2023 ACM A.M. Turing Award मिला। उन्हें computation theory में बुनियादी योगदान, खासकर computation में randomness की भूमिका की समझ को नए सिरे से परिभाषित करने और theoretical computer science क्षेत्र में दशकों तक बौद्धिक नेतृत्व दिखाने के लिए सम्मानित किया गया।

• Wigderson computation complexity theory, algorithms और optimization, randomness और cryptography, parallel और distributed computing, combinatorics, graph theory जैसे क्षेत्रों में अग्रणी रहे हैं, और उन्होंने theoretical computer science तथा mathematics और science के बीच एक कड़ी की भूमिका भी निभाई है।

• Wigderson की प्रमुख उपलब्धियों में से एक randomness और computational hardness के बीच चौंकाने वाला संबंध खोज निकालना है। उनके शोध ने दिखाया कि efficient computation के लिए randomness अनिवार्य नहीं है।

• 2021 में उन्होंने Abel Prize भी जीता, जिससे वे theoretical/abstract mathematics और computer science के सर्वोच्च सम्मानों, दोनों को पाने वाले विशिष्ट व्यक्तित्व बन गए।

• उनकी पुस्तक "Mathematics and Computation" हाल ही में प्रकाशित हुई है और उसे अच्छी सराहना मिल रही है।

• उनके शोध निष्कर्षों के अनुसार, यदि किसी proposition को prove किया जा सकता है, तो zero-knowledge proof भी संभव है; और यदि pseudorandom numbers को probabilistic algorithms में लागू किया जाए, तो उसी समस्या के लिए efficient deterministic algorithms प्राप्त किए जा सकते हैं। इससे संकेत मिलता है कि AI जैसे probabilistic computation models की complexity को काफी कम किया जा सकता है।