連接數(shù)學(xué)和計算機(jī)科學(xué)的先驅(qū)--阿維·維格森
阿貝爾獎和圖靈獎常被稱為數(shù)學(xué)界和計算機(jī)界的諾貝爾獎。此前，從未有人同時取得這兩個大獎，直到現(xiàn)在，數(shù)學(xué)家阿維·維格森（Avi Wigderson）成為了史上首個榮獲這兩個獎項的科學(xué)家。
4月10日，美國計算機(jī)學(xué)會（ACM）宣布將2023年圖靈獎授予維格森，以表彰他對計算理論的基礎(chǔ)性貢獻(xiàn)。維格森的工作幾乎觸及了這一學(xué)科的每一個領(lǐng)域。他的同事、合作者和學(xué)員都說，他總是能在不同的領(lǐng)域之間發(fā)現(xiàn)意想不到的橋梁。從20世紀(jì)90年代開始，他對隨機(jī)性和計算所展開的研究工作，就為數(shù)學(xué)和計算機(jī)科學(xué)之間建立了深刻的聯(lián)系。
1956年，維格森出生在以色列海法。他是計算復(fù)雜性理論、算法和優(yōu)化、隨機(jī)性和密碼學(xué)、并行和分布式計算、組合學(xué)、圖論等領(lǐng)域的先驅(qū)。除了剛剛榮獲的圖靈獎，他還與洛瓦茲·拉茲洛 （Lovász László）在2021年一同榮獲了數(shù)學(xué)領(lǐng)域的最高獎——阿貝爾獎。（圖/Peter Badge）
隨機(jī)性與確定性
從本質(zhì)上說，計算機(jī)是確定性系統(tǒng)。確定性算法遵循的是可預(yù)測的模式。相比之下，隨機(jī)性缺乏明確的模式，或者說缺乏對事件或結(jié)果的可預(yù)測性。
在20世紀(jì)70年代末，許多計算機(jī)科學(xué)家已經(jīng)意識到，對于許多難題，采用隨機(jī)性的算法，即概率算法，遠(yuǎn)勝于確定性算法。許多沒有有效確定性算法的問題，都可以被概率算法有效地解決，盡管存在一些小的出錯率。
隨機(jī)性的令人驚訝的有效性，引發(fā)計算機(jī)科學(xué)家思考隨機(jī)性本身的本質(zhì)，他們開始質(zhì)疑隨機(jī)性對于有效解決問題有多必要，以及在什么情況下它是可以被完全移除的。
這些問題，以及許多其他相關(guān)的基本問題，是理解計算中隨機(jī)和偽隨機(jī)的核心。更好地理解計算中的隨機(jī)動態(tài)，有助于科學(xué)家開展出更好的算法，并加深對計算的本質(zhì)的理解。
維格森的貢獻(xiàn)
維格森在計算機(jī)科學(xué)的各個領(lǐng)域都作出了廣泛而深刻的貢獻(xiàn)，而他將隨機(jī)性與困難問題聯(lián)系起來的工作，可能是其中最為顯著的成就。
維格森與合作者發(fā)表了一系列極具影響力的論文。在20世紀(jì)90年代發(fā)表的兩篇論文中，他與合作者證明了在特定的假設(shè)下，對于高效計算來說，隨機(jī)性并不是必需的。
他們提出了一個有點(diǎn)類似于P≠NP的猜想，P=BPP，這個等式意味著每個隨機(jī)算法都可以被去隨機(jī)化，并轉(zhuǎn)化為具有可觀效率的確定性算法；此外，去隨機(jī)化是通用且普遍的，它不依賴于隨機(jī)化算法的內(nèi)部細(xì)節(jié)。
另一種看待這個問題的方式是將其視為難度和隨機(jī)性之間的權(quán)衡：如果存在一個足夠困難的問題，那么隨機(jī)性就可以順利獲得高效的確定性算法進(jìn)行模擬。維格森隨后證明了與之相反的觀點(diǎn)，他得出的結(jié)論認(rèn)為：即使是針對具有已知隨機(jī)算法的特定問題的有效確定性算法，也意味著一定存在這樣一個困難問題。
這一工作與偽隨機(jī)（看起來隨機(jī)）的對象緊密相關(guān)。維格森的工作構(gòu)建了偽隨機(jī)生成器，它將幾個真正隨機(jī)的比特變成許多偽隨機(jī)比特，從一個不完美的隨機(jī)源中提取出近乎完美的隨機(jī)比特。
維格森的這些工作的影響，遠(yuǎn)遠(yuǎn)超出了隨機(jī)和去隨機(jī)領(lǐng)域。他的這些想法隨后被應(yīng)用于理論計算機(jī)科學(xué)的眾多領(lǐng)域。
維格森并沒有止步于此，他仍致力于研究計算隨機(jī)性的廣泛領(lǐng)域。在另一組論文中，他給出了擴(kuò)展圖（具有強(qiáng)連通性的稀疏圖）的第一個有效的組合結(jié)構(gòu)，這些擴(kuò)展圖在數(shù)學(xué)和理論計算機(jī)科學(xué)中都有許多重要應(yīng)用。
指導(dǎo)與傳承
除了在學(xué)術(shù)上做出了突破性的貢獻(xiàn)外，維格森還被公認(rèn)為一位受人尊敬的導(dǎo)師和同事，他為無數(shù)年輕的研究人員無私地給予建議。他淵博的知識和無與倫比的技術(shù)，加上他的友好、熱情和慷慨，吸引了許多最優(yōu)秀的年輕人從事理論計算機(jī)科學(xué)的研究。
關(guān)注微博
關(guān)注微信
關(guān)注公眾號
關(guān)注抖音號