以色列數學家威格森獲阿貝爾獎,曾擔任阿里達摩院十大祖師

語言: CN / TW / HK

剛剛,挪威科學與文學院公佈了年度阿貝爾獎的獲得者是阿維·威格森(Avi Wigderson)和洛瓦茲·拉茲洛 (Lovász László),以表彰他們在「理論電腦科學和離散數學方面做出的傑出貢獻,以及使其在現代數學中心領域中發揮主導作用。」

阿貝爾獎是數學界的最高榮譽之一,被稱為數學界的諾貝爾獎,與菲爾茲獎齊名,前者主要吸引年輕人從事數學研究,一起擴大數學的影響是阿貝爾獎設立的主要目的。

曾獲過這個獎項的數學家包括證明費馬大定理的懷爾斯(Andreww J. Wiles)、電影《美麗心靈》原型約翰·納什(John Nash),以及目前唯一一位女性獲得者凱倫·烏倫貝克(Karen Keskulla Uhlenbeck)等。

曾幾何時,電腦科學和純數學幾乎是完全獨立的學科。如今,它們之間的距離是如此之近,以至於很難找到它們之間的界線。

Avi在計算機方面有卓越成果,而Lovász則在數學的天才,他們的研究相互交錯,對理解計算中的隨機性和探索高效計算的邊界做出了巨大貢獻。

他們在2012年的阿貝爾頒獎禮上聊天,10年後,他們將分享這一大獎

Avi Wigderson:「去隨機化」的以色列計算機學家

威格森1956年出生於以色列海法。

在他十幾歲的時候,電腦科學家剛剛開始勾畫一個基本的理論框架——複雜性理論,涉及根據演算法解決計算問題的難易程度對其進行分類。而衡量難度的主要標準是計算步驟的數量,最基本的區別是「易」與「難」。

一個簡單的計算問題的例子是將兩個數相乘。無論數字變得多麼大,計算機都能很快找到它們的乘積。這個問題屬於複雜度類「P」,它包含了所有容易解決的計算問題。

相比之下,有些計算問題則看起來很難,比如,尋找一個數的質因數(prime factor,能整除給定正整數的質數)。

目前,已知演算法還沒有能快速做到這一點的。但反過來就容易多了,如果你知道了某個數的質因數,只要把它們乘在一起,你就知道它們是正確的。這個問題屬於「NP」,它包含的計算問題可能很難解決,但其答案很容易驗證。

這也被稱為「去隨機化」,從這裡開始,人們開始認真思考隨機性也沒那麼重要。

20世紀70年代初,電腦科學家提出了複雜性理論的指導性猜想,問P中的問題列表是否與NP中的問題完全對應,也就是之後爭論不休的:複雜度類P和NP是否是等價的(P=NP?)

這也是讓威格森初露鋒芒的地方。

1977年,當威格森進入以色列理工學院時,這個問題還很「時髦」。

在接下來的幾十年裡,他幫助闡述了將複雜性類別一一歸位。

後來,威格森發表了兩篇論文,在人們普遍認可的計算假設下,每個概率多項式時間演算法都可以完全去隨機化(derandomized)。換句話說,多項式時間計算不需要隨機性,總是有可能將快速隨機演算法轉換為快速確定性演算法。

結果確定了稱為BPP的複雜度類與P完全相同,也就是P = BPP,將數十年來對隨機演算法的研究巧妙地結合到了複雜性理論的主體中,並改變了電腦科學家看待隨機演算法的方式。

他還在其職業生涯早期對網際網路密碼學做出了貢獻,包括現在用於加密貨幣技術的零知識證明。

當然,威格森一直活躍在學術崗位。

1983年,威格森在普林斯頓大學獲得博士學位。隨後,他在加州大學伯克利分校擔任客座助理教授,在IBM擔任訪問科學家,並在伯克利的數學科學研究所(MSRI)擔任研究員,1986年加入希伯來大學(Hebrew University)擔任教員。自1999年以來,Wigderson一直是高等研究院數學學院的教授。Wigderson還在2009年獲得哥德爾獎(Godel Prize),獲獎原因是他與Omer Reingold和Salil Vadhan合作的工作,並在1994年獲得了內萬林納獎(Nevanlinna Prize)。

2018,威格森因對電腦科學和數學理論的貢獻(Institute for Advanced Study)當選ACM Fellow,他還是首批坐鎮阿里達摩院的十位「達摩祖師」之一。

Lovász László:數學明星、LLL演算法創始人

洛瓦茲1948年出生在布達佩斯,從小就算是數學界的明星。

十幾歲時,他就三塊金牌加深:1964年、1965年及1966年國際數學奧林匹克競賽金牌。22歲,洛瓦茲獲得於布達佩斯羅蘭大學電腦科學博士學位。

在他年輕的時候,洛瓦茲遇到了他的伯樂:匈牙利數學家Paul Erdős,後者幫助他進入了圖論領域。

在當時,圖論是一個數學上的「寶藏」,以提出一些有趣的問題而聞名,比如四色猜想(現在是一個已被證明的定理),在任何地圖上,是否總能用四種顏色給國家上色,並且沒有兩個相鄰的國家有相同的顏色。

洛瓦茲研究的主要影響之一是確立了離散數學能夠解決電腦科學基本理論問題的方法。他說,「能夠親身經歷一段數學發展與應用領域完全契合的時期,感到非常幸運。」

洛瓦茲的許多工作都集中在解決各種問題的演算法的開發上。他最有影響的結果之一是LLL演算法,該演算法以其洛瓦茲以及Arjen和Hendrik Lenstra兄弟命名。該演算法適用於被稱為格的幾何物件,這些幾何物件是空間中的點集,其座標通常具有整數值。

LLL演算法解決了有關其屬性的一個基本問題:晶格中的哪個點最接近原點?這是一個通常很難解決的簡單問題,尤其是在高維空間中以及晶格中的點何時形成扭曲的形狀。

目前,唯一已知能夠承受量子計算機攻擊的加密系統正是基於 LLL 演算法。

洛瓦茲榮獲過多個獎項,包括 1999 年沃爾夫獎、1999 年高德納獎、2001 年哥德爾獎和2010年京都獎。2007年至2010年,洛瓦茲擔任國際數學聯盟主席。他還於2014年至2020年擔任匈牙利科學院院長,在這些年裡,他為阻止匈牙利政府接管該學院的研究機構而做出了大膽的努力,他和其他許多人認為,此舉將降低研究人員的獨立性。

遺憾的是,他們最終沒有成功。

自從2003年授予阿貝爾獎以來,洛瓦茲是第三位在匈牙利出生的人,而威格森則是第二位以色列人,獲獎者將獲得獎金約750萬挪威克朗(約合人民幣575萬元)。

分享到: