2023 का ACM Turing Award प्रोफेसर Avi Wigderson को प्रदान किया गया
(awards.acm.org)- ACM ने Avi Wigderson को 2023 ACM A.M. Turing Award का विजेता चुना है, उनके उस योगदान को मान्यता देते हुए जिसने computation theory और computation में randomness की भूमिका को नए सिरे से समझाया
- Wigderson Institute for Advanced Study में Herbert H. Maass Professor हैं, और computational complexity theory, algorithms, cryptography, parallel और distributed computing, combinatorics, और graph theory को व्यापक रूप से आगे बढ़ाने वाले व्यक्ति हैं
- उनका मुख्य योगदान hardness for randomness पर शोध है, जिसमें उन्होंने दिखाया कि व्यापक रूप से मानी जाने वाली computational assumptions के तहत randomized polynomial-time algorithms को deterministically simulate किया जा सकता है
- संबंधित papers ने pseudorandom generators, BPP के subexponential-time simulations, और hardness-vs-randomness tradeoff प्रस्तुत किए, जिनका theoretical computer science के कई क्षेत्रों पर प्रभाव पड़ा
- Turing Award में Google के समर्थन से 10 लाख डॉलर की पुरस्कार राशि दी जाती है, और Wigderson को तकनीकी उपलब्धियों के साथ-साथ युवा researchers का मार्गदर्शन करने वाले mentor के रूप में भी सराहा गया है
ACM Turing Award मिलने की पृष्ठभूमि
- ACM ने Avi Wigderson को 2023 ACM A.M. Turing Award का विजेता चुना
- पुरस्कार का कारण computation theory में बुनियादी योगदान, computation में randomness की भूमिका की समझ को नए रूप में स्थापित करने वाली उपलब्धियां, और theoretical computer science में कई दशकों की बौद्धिक नेतृत्वकारी भूमिका है
- Wigderson न्यू जर्सी के Princeton स्थित Institute for Advanced Study के mathematics department में Herbert H. Maass Professor हैं
-
प्रमुख कार्यक्षेत्र
- Computational complexity theory
- Algorithms और optimization
- Randomness और cryptography
- Parallel और distributed computing
- Combinatorics और graph theory
- Theoretical computer science तथा mathematics और science के बीच संबंध
- ACM A.M. Turing Award को “computing का Nobel Prize” कहा जाता है, और Google, Inc. की वित्तीय सहायता से 10 लाख डॉलर की पुरस्कार राशि दी जाती है
- यह पुरस्कार computing की mathematical foundations स्थापित करने वाले British mathematician Alan M. Turing के नाम पर रखा गया है
Theoretical computer science किन सवालों से जुड़ी है
- Theoretical computer science computer science की mathematical नींव से जुड़ी है, और “क्या यह problem computation से हल हो सकती है”, “अगर हल हो सकती है तो कितना समय और resources लगेंगे” जैसे सवालों से निपटती है
- यह क्षेत्र efficient algorithms design करने के सिद्धांतों की भी खोज करता है
- Algorithms रोजमर्रा में इस्तेमाल होने वाली computing technologies को संभव बनाने वाली बुनियाद हैं
- Theoretical computer science ऐसे बौद्धिक challenges से भी जुड़ी है जो तुरंत practical applications को बेहतर नहीं बनाते, लेकिन research breakthroughs कई क्षेत्रों में प्रगति की ओर ले जा सकते हैं
- Cryptography
- Computational biology
- Network design
- Machine learning
- Quantum computing
Computation में randomness क्यों महत्वपूर्ण है
- Computers मूल रूप से deterministic systems हैं, और किसी दिए गए input के लिए algorithm का instruction set computation और output को uniquely तय करता है
- Randomness का मतलब events या outcomes में स्पष्ट pattern या predictability का न होना है
- वास्तविक दुनिया में weather systems, biological phenomena, और quantum phenomena जैसी कई घटनाएं random दिखती हैं
- Computer scientists ने efficiency बढ़ाने के लिए algorithms को computation के दौरान random choices करने की क्षमता तक विस्तार दिया है
- जिन कई समस्याओं के लिए efficient deterministic algorithm ज्ञात नहीं था, उन्हें भी छोटे error probability वाले randomized algorithms से efficiently हल किया जा सकता है
- इस error probability को efficiently कम किया जा सकता है
- मुख्य सवाल यह है कि क्या randomness अनिवार्य है, क्या इसे हटाया जा सकता है, और randomized algorithms की सफलता के लिए किस quality की randomness चाहिए
- Computation में randomness और pseudorandomness के व्यवहार को बेहतर समझने से बेहतर algorithms विकसित करने और computation की प्रकृति को समझने में मदद मिल सकती है
Wigderson के मुख्य शोध योगदान
- Wigderson ने 40 वर्षों तक theoretical computer science research का नेतृत्व किया है, और computation में randomness और pseudorandomness की भूमिका समझने में बुनियादी योगदान दिए हैं
- Computer scientists ने randomness और computational hardness, यानी ऐसी natural problems की पहचान जिनके लिए efficient algorithms नहीं हैं, के बीच महत्वपूर्ण connection खोजा
- Wigderson और उनके collaborators ने hardness for randomness पर प्रभावशाली शोध प्रकाशित किए
- इन शोधों ने दिखाया कि standard और व्यापक रूप से मानी जाने वाली computational assumptions के तहत सभी randomized polynomial-time algorithms को efficiently derandomize किया जा सकता है
- यह परिणाम दिखाता है कि efficient computation के लिए randomness जरूरी नहीं भी हो सकती है
- इस research stream ने computation में randomness की भूमिका और randomness के बारे में सोचने के तरीके को बदल दिया
-
3 प्रतिनिधि papers
- Hardness vs. Randomness
- Noam Nisan के साथ सह-लेखित
- एक नए प्रकार के pseudorandom generator को पेश किया
- साबित किया कि पहले की तुलना में कहीं कमजोर assumptions के तहत random algorithms की efficient deterministic simulation संभव है
- BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs
- László Babai, Lance Fortnow, और Noam Nisan के साथ सह-लेखित
- hardness amplification का उपयोग किया
- दिखाया कि कमजोर assumptions के तहत bounded-error probabilistic polynomial time, यानी BPP, infinitely many input lengths के लिए subexponential time में simulate किया जा सकता है
- P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma
- Russell Impagliazzo के साथ सह-लेखित
- अधिक शक्तिशाली pseudorandom generator पेश किया
- लगभग optimal hardness-vs-randomness tradeoff प्रस्तुत किया
- Hardness vs. Randomness
प्रभाव का दायरा और अतिरिक्त उपलब्धियां
- Wigderson के तीन papers ने randomness और derandomization के क्षेत्र से आगे बढ़कर theoretical computer science के कई क्षेत्रों को प्रभावित किया
- इन papers के ideas का बाद में कई प्रमुख researchers के प्रभावशाली papers में उपयोग हुआ
- Omer Reingold, Salil Vadhan, और Michael Capalbo के साथ paper में expander graph का पहला efficient combinatorial construction प्रस्तुत किया गया
- expander graph मजबूत connectivity properties वाला sparse graph होता है
- mathematics और theoretical computer science दोनों में इसके महत्वपूर्ण applications हैं
- Randomness के अलावा, Wigderson ने निम्न क्षेत्रों में बौद्धिक नेतृत्व दिखाया
- multi-prover interactive proofs
- cryptography
- circuit complexity
Mentoring और मूल्यांकन
- Wigderson को groundbreaking technical contributions के साथ-साथ कई युवा researchers का मार्गदर्शन करने वाले सम्मानित mentor और colleague के रूप में भी पहचाना जाता है
- उनका विशाल ज्ञान, technical ability, सहजता, उत्साह और उदारता ऐसे तत्व माने जाते हैं जिन्होंने उत्कृष्ट युवा researchers को theoretical computer science में career बनाने के लिए प्रेरित किया
- ACM President Yannis Ioannidis ने बताया कि Wigderson को Abel Prize भी मिला है, जिसे mathematics में lifetime achievement के सबसे महत्वपूर्ण सम्मानों में माना जाता है
- Ioannidis ने कहा कि mathematics computer science की नींव है, और Wigderson के काम ने mathematics के विविध subfields को theoretical computer science से जोड़ा
- Google Senior Vice President Jeff Dean ने कहा कि Wigderson के randomness और अन्य विषयों पर research ने पिछले 30 वर्षों में theoretical computer science का agenda तय किया
- Dean ने यह भी रेखांकित किया कि Wigderson ऐसे mentor रहे जिन्होंने ideas और research directions बनाए, और युवा researchers को उन दिशाओं में research करने के लिए प्रेरित किया
Turing Award और Wigderson के अतिरिक्त प्रमुख papers
- A.M. Turing Award ने 1966 में शुरू होने के बाद से information technology industry को आगे बढ़ाने वाले systems और theoretical foundations बनाने वाले computer scientists और engineers को सम्मानित किया है
- Wigderson के पुरस्कारों में ये शामिल हैं
- Abel Prize
- IMU Abacus Medal, जिसका पुराना नाम Nevanlinna Prize था
- Donald E. Knuth Prize
- Edsger W. Dijkstra Prize in Distributed Computing
- Gödel Prize
- Wigderson ACM Fellow हैं, और U.S. National Academy of Sciences तथा American Academy of Arts and Sciences के सदस्य हैं
-
अतिरिक्त प्रमुख papers
- In Search of an Easy Witness: Exponential Time vs Probabilistic Polynomial Time
- Russell Impagliazzo और Valentine Kabanets के साथ सह-लेखित
- exponential time और probabilistic polynomial time complexity classes के complexity संबंधों पर कई परिणाम स्थापित किए
- Randomness vs. Time: De-Randomization Under a Uniform Assumption
- Russell Impagliazzo के साथ सह-लेखित
- साबित किया कि अगर BPP≠EXP है, तो BPP की सभी problems को लगभग सभी inputs पर deterministic subexponential time में हल किया जा सकता है
- Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions
- Michael Ben-Or, Shafi Goldwasser, और Joe Kilian के साथ सह-लेखित
- साबित किया कि सभी NP languages के पास complete zero-knowledge proof systems होते हैं
- Proofs That Yield Nothing but Their Validity or All Languages in NP Have Zero-Knowledge Proof Systems
- Oded Goldreich और Silvio Micali के साथ सह-लेखित
- दिखाया कि secure cryptographic functions के अस्तित्व की assumption या information छिपाने वाले physical means का उपयोग करके सभी NP languages के पास zero-knowledge proofs होते हैं
- In Search of an Easy Witness: Exponential Time vs Probabilistic Polynomial Time
1 टिप्पणियां
Hacker News की रायें
घोषणा में जिन Wigderson के दो प्रमुख पेपरों का ज़िक्र था, वे Noam Nisan के साथ सह-लेखित हैं, जो मशहूर ऑनलाइन कोर्स From Nand to Tetris बनाने वाले प्रोफेसरों में से एक हैं
यह भी अच्छा लगता है कि एक व्यक्ति इतनी विविध उपलब्धियां हासिल कर सकता है, और वह सिस्टम भी प्रभावशाली है जिसने ऐसी flexibility की अनुमति दी
Quanta का एक अच्छा लेख भी है: https://www.quantamagazine.org/avi-wigderson-complexity-theo...
Wigderson से करवाए गए तरह-तरह के pose मज़ेदार लगे। बहुत awkward दिखते हैं। कुछ ऐसा जैसे, “अच्छा, इस कुर्सी पर बैठिए और खिड़की से बाहर गहरी नज़रों से देखिए”
मेरी समझ में complexity classes worst-case performance से जुड़ी होती हैं, इसलिए मोटे तौर पर जानना चाहूंगा कि अच्छे pseudorandom generators और अच्छे randomized algorithms होने पर भी यह कैसे साबित किया जाता है कि
RNG + seed + problem instanceका कोई भी combination exponential time नहीं लेतासोच रहा हूं कि reporter ने इसे कैसे confuse कर दिया
Scott Aaronson ने लिखा है कि Avi Wigderson के एक lecture ने उनके career path पर कैसे असर डाला: https://scottaaronson.blog/?p=2925
“Israeli Wins Turing Prize, Computing's Highest Honor, for Insights on Randomness” में और जानकारी है: [1] और archived copy [2]
[1] https://www.haaretz.com/israel-news/2024-04-10/ty-article/.p...
[2] https://archive.is/e8uix
Wigderson के research में hardness vs randomness tradeoff वाली दिशा समझनी हो तो कहां से शुरू करना अच्छा रहेगा, यह जानना चाहूंगा
Turing Award winner का नाम कभी न सुना हो, ऐसा अक्सर नहीं होता, लेकिन यह व्यक्ति मेरी नज़र से पूरी तरह बाहर था
शायद इसका मतलब यह है कि NP-complete problems के लिए probabilistic approximation भी polynomial time में नहीं है, या फिर randomness हटाए गए version को भी approximation algorithm ही कहा जा रहा है—इस पर confusion है
अभी-अभी Wigderson की किताब उठाई है और अब तक पसंद आ रही है: https://press.princeton.edu/books/hardcover/9780691189130/ma...
जिन लोगों की computer science/math undergraduate background थोड़ी rusty हो गई है, उनके लिए computational topics को ज्यादा बुनियादी स्तर पर समझाने वाली कोई किताब recommend कर सकते हैं?
संबंधित लेख में यह वाक्य है: https://www.quantamagazine.org/avi-wigderson-complexity-theo...
“अगर कोई proposition provable है, तो उसका zero-knowledge proof भी होता है”—यह तो दिमाग घुमा देने वाला है
और “random bits की जगह pseudorandom bits को probabilistic algorithm में डाल दें तो वही problem के लिए efficient deterministic algorithm बन जाता है”—यह भी अविश्वसनीय रूप से चौंकाने वाला है
AI भी probabilistic computation है, तो अगर मैं सही पढ़ रहा हूं, क्या इसका मतलब यह नहीं कि मौजूदा models की complexity कई orders of magnitude तक घटाई जा सकती है? अगर यह beginner की गलतफहमी है तो कोई मुझे इससे बाहर निकाले
कुछ अपवाद हैं, जैसे efficiency बढ़ाने के लिए analog computation इस्तेमाल करने वाले अजीब AI accelerator chips
दूसरी बात, जो deterministic algorithm बनता है वह randomized algorithm की तुलना में काफी कम efficient होता है। बस कमजोर assumptions के तहत वह उसी complexity class में आता है
लेख का यह हिस्सा अच्छा लगा: “applications motivation नहीं हैं, लेकिन हम जानते हैं कि foundational research में भी उपयोगिता मिल सकती है। Alan Turing को देखिए। उन्होंने Entscheidungsproblem पर logic/mathematics paper एक कम-ज्ञात journal में लिखा था। applications motivation नहीं थीं”
यह Feynman की plate वाली anecdote जैसा है। university cafeteria में देखी गई चीज़ पर casual reaction से शुरुआत हुई और आखिरकार Nobel Prize तक पहुंची
बात को और व्यापक करें तो, आधुनिक academia ऐसी curiosity-driven exploration को दबाने की दिशा में जा रही है
ACM के अनुसार, Avi Wigderson को computation में randomness की भूमिका की समझ को नया आकार देने सहित computational theory में foundational contributions और theoretical computer science में दशकों की intellectual leadership के लिए 2023 ACM A.M. Turing Award का विजेता चुना गया
Wigderson, New Jersey के Princeton में Institute for Advanced Study के School of Mathematics में Herbert H. Maass Professor हैं, और computational complexity theory, algorithms and optimization, randomness and cryptography, parallel और distributed computing, combinatorics, graph theory, तथा theoretical computer science और mathematics/science के संबंधों जैसे क्षेत्रों में केंद्रीय हस्ती रहे हैं
2021 में उन्हें Abel Prize भी मिला था, जिससे वे theoretical/abstract mathematics और computer science के सर्वोच्च सम्मानों को साथ पाने वाले काफी अनोखे उदाहरण बन गए
सरल उदाहरण के लिए MIT के theoretical computer science courses की सूची https://catalog.mit.edu/subjects/6/ देखें, तो पता चलता है कि कितने courses mathematics वाले course 18 के साथ cross-listed हैं
हालांकि मैं इस पर बोलने वाला कौन होता हूं
probability/randomness और computation विषय पर beginner-friendly से लेकर advanced तक पढ़ने लायक resources की recommendations चाहिए
Google पर Eli Upfal और Michael Mitzenmacher की “Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis” मिलती है, लेकिन beginner/introductory books, articles या videos अच्छे से नहीं मिल पा रहे हैं