2023年圖靈獎(jiǎng)揭曉！普林斯頓數(shù)學(xué)教授，成史上首位阿貝爾獎(jiǎng)雙料獲獎(jiǎng)?wù)?
2023年圖靈獎(jiǎng)，剛剛揭曉！
獲得這屆「計(jì)算機(jī)界諾貝爾獎(jiǎng)」——ACM A.M.圖靈獎(jiǎng)的，就是普林斯頓高等研究院數(shù)學(xué)學(xué)院的教授Avi Wigderson。
表彰的是Wigderson在計(jì)算理論領(lǐng)域的開創(chuàng)性貢獻(xiàn)，特別是他對(duì)計(jì)算中隨機(jī)性角色的重新定義，以及他在理論計(jì)算機(jī)科學(xué)領(lǐng)域數(shù)十年的引領(lǐng)。
不僅如此，這一榮譽(yù)也使Avi Wigderson成為了，歷史上第一位同時(shí)獲得圖靈獎(jiǎng)和阿貝爾獎(jiǎng)的人。
阿貝爾獎(jiǎng)被視為數(shù)學(xué)領(lǐng)域的最高榮譽(yù)
Wigderson是普林斯頓高級(jí)研究院數(shù)學(xué)學(xué)院的Herbert H. Maass教授。
他在計(jì)算復(fù)雜性理論、算法與優(yōu)化、隨機(jī)性與密碼學(xué)、并行與分布式計(jì)算、組合學(xué)和圖論等領(lǐng)域均有突出貢獻(xiàn)，并且在理論計(jì)算機(jī)科學(xué)與數(shù)學(xué)及科學(xué)的交叉領(lǐng)域中，也具有重要影響。
最終，他將獲得高達(dá)100萬(wàn)美元的獎(jiǎng)金。
計(jì)算中的隨機(jī)性和偽隨機(jī)性
過去四十年里，Wigderson對(duì)于理解計(jì)算中的隨機(jī)性和偽隨機(jī)性，做出了開創(chuàng)性貢獻(xiàn)。
此前，計(jì)算機(jī)科學(xué)家們已經(jīng)發(fā)現(xiàn)，隨機(jī)性與計(jì)算難度之間存在顯著的聯(lián)系，比如，一些自然問題并沒有高效的算法解決方案。
而Wigderson與同事合作撰寫了一系列研究，通過增加計(jì)算難度，來減少算法中的隨機(jī)性需求。
這些研究，對(duì)于學(xué)界具有深遠(yuǎn)的影響。
他們成功地證明了，在一些廣泛認(rèn)可的計(jì)算假設(shè)下，所有的概率多項(xiàng)式時(shí)間算法，都可以被有效轉(zhuǎn)化為確定性算法。
也即是說，高效的計(jì)算并不依賴于隨機(jī)性。
從此，我們對(duì)于計(jì)算中隨機(jī)性作用的理解被徹底改變。
以下就是三篇極具影響力的論文——
- 「Hardness vs. Randomness」（與Noam Nisan合著）
這篇論文不僅引入了一種新型偽隨機(jī)發(fā)生器，而且還證明了：在比以前所知更弱的假設(shè)下，可以對(duì)隨機(jī)算法進(jìn)行高效確定性模擬。
- 「BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs」（與László Babai、Lance Fortnow和Noam Nisan合著）
這篇論文利用「難度放大」，證明了在弱假設(shè)下，可以在亞指數(shù)時(shí)間內(nèi)模擬無(wú)限多輸入長(zhǎng)度的有限錯(cuò)誤概率多項(xiàng)式時(shí)間（BPP）。
- 「P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma」（與Russell Impagliazzo合著）
這篇論文介紹了一種更強(qiáng)的偽隨機(jī)發(fā)生器，它在本質(zhì)上實(shí)現(xiàn)了難度與隨機(jī)性之間的最優(yōu)權(quán)衡。
Wigderson的這三篇論文，其理論被廣泛應(yīng)用于理論計(jì)算機(jī)科學(xué)的多個(gè)分支，并且激發(fā)了多位專家的重要研究。
在計(jì)算中隨機(jī)性的廣泛領(lǐng)域內(nèi)，Wigderson與Omer Reingold、Salil Vadhan和Michael Capalbo合作，首次高效構(gòu)造了展開圖，這些圖具有出色的稀疏性和連通性，廣泛應(yīng)用于數(shù)學(xué)和理論計(jì)算機(jī)科學(xué)中。
除了隨機(jī)性研究，Wigderson還在多證明者交互式證明、密碼學(xué)和電路復(fù)雜度等多個(gè)理論計(jì)算機(jī)科學(xué)領(lǐng)域，發(fā)揮了重要的領(lǐng)導(dǎo)作用。
此外，他作為導(dǎo)師和同事也備受贊譽(yù)。他的親和力、熱情和慷慨，吸引了眾多青年學(xué)者，投身理論計(jì)算機(jī)科學(xué)領(lǐng)域。
復(fù)雜性理論先驅(qū)
作為一名計(jì)算復(fù)雜性理論家，相比于問題的答案，讓Avi Wigderson更感興趣的是，這些問題是否有解決方案？以及，該如何進(jìn)行判斷？
「對(duì)于我們正在面對(duì)并嘗試解決的每一個(gè)問題，都不能排除存在一種能夠解決它的算法。這是我認(rèn)為最有趣的問題?！?/p>
如今，Wigderson憑借著在計(jì)算理論基礎(chǔ)上的杰出貢獻(xiàn)，榮獲了公認(rèn)的最高榮譽(yù)之一——ACM A.M.圖靈獎(jiǎng)。
Wigderson的父親非常熱愛拼圖和數(shù)學(xué)基本原理。
而在以色列海法長(zhǎng)大的Wigderson，深受父親的影響，
「他讓我對(duì)這個(gè)領(lǐng)域產(chǎn)生了濃厚的興趣，」Wigderson回憶道。
1970年代，Wigderson在海法大學(xué)開始了大學(xué)生涯。
最初他本主修數(shù)學(xué)，但在父母的建議下轉(zhuǎn)向了計(jì)算機(jī)科學(xué)。而這背后的原因很樸素——他的父母認(rèn)為，這個(gè)專業(yè)更好找工作。
雖然沒去成數(shù)學(xué)專業(yè)，但Wigderson很快就發(fā)現(xiàn)，計(jì)算機(jī)科學(xué)是一個(gè)充滿了未解之謎的領(lǐng)域，而這些謎題，本質(zhì)上都與數(shù)學(xué)相關(guān)。
他早期的一項(xiàng)開創(chuàng)性工作，正是探討這樣一個(gè)看似矛盾的問題——
能否在不展示證明過程的情況下讓人相信：一個(gè)數(shù)學(xué)命題已經(jīng)得到了證明？
1985年，Shafi Goldwasser、Silvio Micali和Charles Rackoff首次提出了零知識(shí)交互證明的概念，并展示了其在若干命題上的應(yīng)用。
后來，Wigderson與Micali和Oded Goldreich一起進(jìn)一步闡述了這一理論，明確了這一點(diǎn)——
如果一個(gè)命題可以被證明，那么它也可以有一個(gè)零知識(shí)證明。
有了零知識(shí)證明，我們就可以證明自己使用密鑰正確加密或簽名了信息，同時(shí)不泄露任何相關(guān)的細(xì)節(jié)。
對(duì)此，普林斯頓大學(xué)的計(jì)算機(jī)科學(xué)家Ran Raz評(píng)價(jià)道：「Avi在密碼學(xué)領(lǐng)域有許多極其重要的成果，而這，就最重要的那個(gè)?！?/p>
不過，Wigderson最最具奠基性的成就，可能在于另一個(gè)領(lǐng)域：將計(jì)算難度與隨機(jī)性相聯(lián)系。
到了1970年代末，計(jì)算機(jī)科學(xué)家們已經(jīng)發(fā)現(xiàn)，對(duì)于許多難題，采用隨機(jī)性算法（也稱為概率算法）會(huì)顯著優(yōu)于傳統(tǒng)的確定性算法。
例如，1977年，Robert Solovay和Volker Strassen提出了一種隨機(jī)算法，可以比當(dāng)時(shí)最好的確定性算法更快地判斷一個(gè)數(shù)字是否為質(zhì)數(shù)。
對(duì)某些問題而言，概率算法則可以引出確定性算法。
在1980年代初，Wigderson與加州大學(xué)伯克利分校的Richard Karp合作，將隨機(jī)性的思想應(yīng)用于那些被認(rèn)為計(jì)算上極其困難的問題，也就是那些不存在已知的確定性算法能在合理時(shí)間內(nèi)解決的問題。
很快，Wigderson和Karp就發(fā)現(xiàn)了一個(gè)難題的隨機(jī)算法，并最終成功將其轉(zhuǎn)化為了確定性算法。
與此同時(shí)，其他研究人也展示了，如何在密碼學(xué)問題中通過計(jì)算難度的假設(shè)來實(shí)現(xiàn)去隨機(jī)化。
由此，Wigderson也和其他人一樣，開始質(zhì)疑在有效解決問題時(shí)隨機(jī)性的必要性，以及在什么條件下可以完全去除隨機(jī)性。
隨后他意識(shí)到，對(duì)隨機(jī)性的需求與問題的計(jì)算難度緊密相連。
在1994年的一篇論文中，Wigderson與計(jì)算機(jī)科學(xué)家Noam Nisan共同證明——
如果真如大多數(shù)計(jì)算機(jī)科學(xué)家所猜測(cè)的那樣，存在自然界中的困難問題，那么，任何高效的隨機(jī)算法都可以被高效的確定性算法替代。
也就是說，隨機(jī)性總是可以被消除的。
更為重要的是，他們發(fā)現(xiàn)確定性算法可能使用「?jìng)坞S機(jī)」序列——這些數(shù)據(jù)串看起來隨機(jī)，但實(shí)際上不是。
同時(shí)，他們還展示了如何利用任意難題來構(gòu)建偽隨機(jī)生成器。即通過將偽隨機(jī)比特（不是真正的隨機(jī)比特）輸入到概率算法中，就可以為同一問題生成一個(gè)高效的確定性算法。
Sudan指出，這篇論文幫助計(jì)算機(jī)科學(xué)家們認(rèn)識(shí)到隨機(jī)性的不同程度，從而幫助揭示了難題的復(fù)雜性及其解決方法?！高@其中的關(guān)鍵不僅僅是隨機(jī)性，而是對(duì)隨機(jī)性的認(rèn)知，」他說。
如今，隨機(jī)性已經(jīng)成為復(fù)雜性理論中的一個(gè)強(qiáng)大工具，但它非常難以捉摸。
Wigderson指出，像硬幣擲出和骰子擲出這樣的行為，并不是真正的隨機(jī)：如果你對(duì)這些物理系統(tǒng)有足夠的了解，那么其結(jié)果是完全可以預(yù)測(cè)的。
但完美的隨機(jī)性既難以捉摸也難以驗(yàn)證。
在過去幾十年里，來自計(jì)算理論的發(fā)現(xiàn)幫助我們深入理解了許多意想不到的問題，從鳥群的集體飛行、選舉結(jié)果到體內(nèi)的生化反應(yīng)。
最后，我們用Wigerson的一句話總結(jié)作為總結(jié)——計(jì)算的應(yīng)用無(wú)處不在。
「基本上，任何自然過程都可以被視為一種演化的計(jì)算過程，因此我們可以從計(jì)算的角度來研究它。可以說，幾乎所有事物都在進(jìn)行某種形式的計(jì)算?！?/p>
Wigerson還曾在2009年獲得了哥德爾獎(jiǎng)。
2018年，Wigerson因?qū)τ?jì)算機(jī)科學(xué)和數(shù)學(xué)理論的貢獻(xiàn)（Institute for Advanced Study）當(dāng)選ACM Fellow。他還在2019年獲得了高德納獎(jiǎng)。
補(bǔ)充知識(shí)
什么是理論計(jì)算機(jī)科學(xué)？
理論計(jì)算機(jī)科學(xué)專注于計(jì)算領(lǐng)域的數(shù)學(xué)基礎(chǔ)。
它探討的問題包括，「這個(gè)問題能否通過計(jì)算來解決？」，以及「如果這個(gè)問題可以通過計(jì)算解決，需要投入多少時(shí)間和其他資源？」
此外，理論計(jì)算機(jī)科學(xué)還致力于設(shè)計(jì)高效的算法。每一項(xiàng)觸及我們生活的計(jì)算技術(shù)都是通過算法實(shí)現(xiàn)的。
深入理解構(gòu)成強(qiáng)大和高效算法的原理，不僅能增進(jìn)我們對(duì)計(jì)算機(jī)科學(xué)的認(rèn)識(shí)，還能幫助我們更好地理解自然規(guī)律。
盡管理論計(jì)算機(jī)科學(xué)以其提供的激動(dòng)人心的智力挑戰(zhàn)而聞名，且通常不直接關(guān)注計(jì)算的實(shí)際應(yīng)用改進(jìn)，但該領(lǐng)域的研究成果已在從密碼學(xué)、計(jì)算生物學(xué)到網(wǎng)絡(luò)設(shè)計(jì)、機(jī)器學(xué)習(xí)及量子計(jì)算等幾乎所有子領(lǐng)域推動(dòng)了顯著進(jìn)展。
為什么隨機(jī)性很重要？
一般來說，計(jì)算機(jī)是確定性系統(tǒng)——算法的指令集對(duì)任何特定輸入都有唯一確定的計(jì)算過程和輸出結(jié)果。
也就是說，確定性算法遵循一個(gè)可預(yù)測(cè)的模式。
然而，隨機(jī)性則不同，它沒有明確的模式，也無(wú)法預(yù)測(cè)事件或結(jié)果的發(fā)生。
鑒于我們所處的世界似乎充斥著隨機(jī)事件（如天氣系統(tǒng)、生物和量子現(xiàn)象等），計(jì)算機(jī)科學(xué)家們通過讓算法在計(jì)算過程中進(jìn)行隨機(jī)選擇，以期提高算法的效率。
事實(shí)上，許多以前沒有有效的確定性算法解決方案的問題，現(xiàn)在通過概率算法得到了有效的解決，雖然這些算法可能會(huì)有小概率的錯(cuò)誤（但這種錯(cuò)誤可以有效地減少）。
但是，隨機(jī)性是否是必要的，還是可以去除它？成功的概率算法需要什么樣的隨機(jī)性？
這些問題以及其他許多基本問題構(gòu)成了理解計(jì)算中隨機(jī)性和偽隨機(jī)性的核心。
更深入地理解計(jì)算中隨機(jī)性的動(dòng)態(tài)可以幫助我們開發(fā)更優(yōu)秀的算法，并深化我們對(duì)計(jì)算本質(zhì)的理解。
本文轉(zhuǎn)自 新智元 ，作者：新智元
