「我也要成為一名理論計算機科學家！」——訪南京大學教授尹一通

2019年10月，南京大學教授尹一通因「在數據複雜性理論和計算相變理論方面所做出的突出貢獻」獲得2019年「CCF-IEEE CS青年科學家獎」。CCCF 動態欄目編委特別採訪了尹一通教授，請他分享在科研教學中的寶貴經驗。

採訪背景：2019年10月，南京大學教授尹一通因「在數據複雜性理論和計算相變理論方面所做出的突出貢獻」獲得2019年「CCF-IEEE CS青年科學家獎」。尹一通於2003年本科畢業於南京大學計算機科學與技術系，2009年博士畢業於耶魯大學計算機科學系，博士畢業後回到南京大學任教至今，現為南京大學計算機軟體新技術國家重點實驗室和計算機科學與技術系教授、博士生導師。他在理論計算機科學國際會議STOC、FOCS、SODA、ICALP、PODC、SPAA與期刊SICOMP、IANDC發表論文二十餘篇，獲SPAA'16優秀論文獎，獲得教育部新世紀優秀人才(2009)、微軟亞洲研究院「鑄星計劃」學者(2011)、中創軟體人才獎(2014)、國家自然科學基金優秀青年科學基金(2017)。CCCF動態欄目編委特別採訪了尹一通教授，請他分享在科研教學中的寶貴經驗。

問：尹教授，首先祝賀您獲得2019 CCF-IEEE CS青年科學家獎，也非常感謝您接受CCCF動態欄目的採訪。您的研究方向是理論計算機科學，能否首先簡單介紹一下您的具體研究領域？

尹一通：我非常榮幸獲得「CCF-IEEE CS青年科學家獎」這個重要的獎項，十分感謝本領域的前輩們對我的支持與認可。很榮幸接受CCCF的採訪。

我的研究方向是理論計算機科學。這在計算機領域是一個基礎性的方向，旨在使用數學工具來探索計算的本質與界限，並為計算相關的問題提供有嚴格理論保障和思維創新的解決方法。傳統上，理論計算機科學因其所使用的數學語言與理論工具的差別，曾一度被大致分為兩大分支：一類是算法和計算複雜性理論，側重依賴組合、概率、分析等偏具體的數學工具；而另一類是程序語言和形式化方法，更加依賴邏輯、代數、範疇論等偏抽象的數學工具。理論計算機科學發展至今，這兩大分支之間的分界也不再明顯。人工智慧與機器學習、量子計算、資料庫、軟體工程、網絡與分布式系統、計算機安全等計算機科學的各個方向幾乎都發展出了與自身實踐相結合的相關理論；同時，物理學、經濟學、社會學等專業的一些研究課題也同理論計算機科學之間產生了交叉。

我的具體研究領域是算法與計算複雜性理論。只要在本科階段上過數據結構和算法相關課程的人，都會接觸過一些這方面的內容。近年來，隨著大數據時代的來臨，計算機科學與技術這門經典學科也面臨著許多變化。一方面，計算的典型形式，由傳統的單個輸入通過至少線性時間複雜度的計算映射到單個輸出，演變為在海量數據上利用亞線性時間複雜度開銷來回答一類參數化的計算和查詢問題。另一方面，計算的目標，也由傳統的判定、優化等關注單個解特性的計算問題，演變為採樣、計數、度量、推斷等關註解空間整體統計性質的統計計算問題。因此，我重點關注針對數據的計算與查詢的複雜性理論，以及統計計算問題的算法與計算複雜性。這兩方面的問題，都展現出了一個有趣的「臨界」現象：針對數據的計算與查詢的時間複雜性會隨著數據存儲與表示的空間複雜性的改變而產生驟然的變化；同時，統計計算問題的計算複雜性也會隨著描述這些問題的參數的連續變化而產生驟然躍遷。這些都是有趣的「計算相變」(computational phase transition)現象。對於臨界計算行為的研究及其理論刻畫，一方面，從科學的角度，可以幫助人們解釋一個計算問題因何而易、又因何而難——這也是計算理論的宗旨；另一方面，從工程的角度，這也可以幫助人們找到能夠達到最優解的那個最「聰明」的算法。

問：在大家看來，理論計算機科學一直是一個很「難啃」的方向，需要有很強的數學背景。能否介紹一下您是如何走上這一研究方向的呢？

尹一通：我是在本科階段萌發了對理論計算機科學的興趣。我本科畢業於南京大學，這是一所理科氛圍濃鬱的高校，因此即便是計算機這種重視應用的專業，「格物致知」的治學態度也滲透在教學的方方面面。我還記得，當年在離散數學的第一堂課上，我的老師宋方敏教授即以莊子的名句「判天地之美，析萬物之理」作為課程的開場白。這句話，曾被日本物理學先驅湯川秀樹拿來作為其治學的準則，也成為了我和許多我們系同學科學觀的一個啟蒙。當我得知，無論人類把計算機造得多麼強大，有許多問題卻仍然是算不出來的，而這種「算不出來」，卻是可以被嚴格證明的。因此，計算也像宇宙中的物質和相互作用的原理一樣，可以作為一種客觀存在而被人類觀察和研究，這一理論對於當年的我而言相當震撼。在南大的課堂上，計算機之於我，從一個很酷、很高級的工具及產業，逐漸轉變為一門美麗而深刻的科學。

本科畢業後，我來到耶魯大學攻讀博士學位。耶魯的計算機系有一個師資強大的理論組，開設了許多很優秀的計算機理論課程。我在第一學期就選了一門難到出名的課程「近似算法」，據說老師還會在作業題裡布置算法領域的頂級會議SODA(ACM-SIAM Symposium on Discrete Algorithms)曾發表過的論文題目。在這些富有挑戰的課程上，我體會到了思維的樂趣以及利用思維創新解決計算機理論問題所帶來的愉悅。理論計算機科學所需的各門類的數學工具會給人一種各種武功秘籍的感覺，而耶魯的計算機理論課程為我打開了通向這個恢弘世界的大門。泡在圖書館裡，我可以查閱到各種久仰的大人物創立的門派學說、發展的體系和數學工具，令我一見如故，愛不釋手。

耶魯是在博士第一年結束時才會讓學生確定導師和研究方向，那時我就毫無疑慮地選擇了這個方向，但是直到臨近博士畢業，才有一種在這個方向終於「出道」了的感覺。中間經歷的過程讓我覺得充滿了痛苦與磨難——我曾經一度只要回想起博士生涯，首先湧入腦海的就是frustration（挫敗）、torment（折磨）這類詞。後來隨著經歷和見識的增長，才知道這其實是一個典型的理科博士的經歷，也是從學生到學者、從行業愛好者到專業人才的成長與蛻變。我是一個很執著的人，對於自己喜歡的事物，即便有許多困難，也願意長久地堅持下來。我也很慶幸我堅持下來了。後來隨著交往的人逐漸增多，我發現即使是那些他人眼中的天才，他們在學術生涯的早期也需要克服類似的障礙；而我自己在別人眼中，竟然已經算順利的了。再後來，我在工作中遇到的許多困難，雖然可能更加複雜並需要付出更加艱辛的努力去克服，但是我覺得這些和當初走上這個研究方向的過程中得到的磨練不能比了。

問：您在耶魯大學拿到博士學位後，直接選擇了回到內地高校任教，您是如何考慮的？

尹一通：在留學期間，我和大多數留學生一樣，並沒有一直想要留在美國，但也沒有想清楚在什麼時間點回國。讀博的前幾年，我還以為畢業後至少會在美國先工作幾年再回國，但沒想到，我在博士畢業後的第一份工作，就是回到我的母校南京大學任教，這也是我至今唯一的全職工作。有人覺得我做這個選擇還挺有勇氣的，尤其在剛回國的頭幾年，因為像我這樣的人確實比較少見。不過從我個人的經歷看來，這還算是一個頗順理成章的決定。

留在學術界的人往往都很重視精神生活，而且學術上的訓練也會培養和提升人在精神層面的追求。在博士剛入學的時候，我跟別人聊天的話題還是諸如「在矽谷工作的起薪多少」「耶魯的助理教授年薪多少」一類的，而等到博士快畢業的時候，話題已經變成這樣了：當年像茅以升這樣一個卡內基梅隆大學（CMU）畢業的工學博士，就能在一窮二白的舊中國時期建造出一座現代化的錢塘江大橋，這足以說明他受到的訓練非常好，水平也非常高，真的令人羨慕和敬佩。

隨著我學術水平的不斷提升，我越來越覺得回到國內大學工作的選擇是正確的。2004年姚期智先生全職到清華工作，2007年我前面提到的耶魯的近似算法課老師、高德納獎(Donald E. Knuth Prize)得主拉維·卡納安(Ravi Kannan)也回到了他的祖國印度，創建了微軟印度研究院的理論組，這些事都對我產生了很大鼓舞。我覺得回到國內大學工作，雖然很難像當年的鄧稼先、茅以升那樣做出那麼功勳卓著的貢獻，但哪怕只是開設出一門原先沒有的理論課程，讓學生普遍能在計算機理論方面得到更好的訓練，也會讓我非常有成就感。

畢業回國這個決定是我和我愛人共同做出的。我愛人是我本科同學，她博士就讀於麻省理工學院(MIT)，研究的方向是大氣科學。我們當時對畢業去向的選擇達成了共識，要滿足三方面的基本約束：第一，不可以離開自己的學術研究；第二，不能最終留在國外一輩子不回國；第三，也是最重要的一條，不可以讓我們倆最終分開。在滿足這三條約束的前提下，回到國內大學工作也就成了最優解。至於當時在薪酬以及其他客觀條件方面的不足，在我們看來都是邊際性(marginal)的，有的還是暫時的，事後證明我們對此的判斷也大體準確。另外，南京大學對我們而言也有特殊的意義，這是我們共同的母校，我們都在這裡遇到了自己喜愛的專業和自己的另一半。能在這裡一起繼續工作、一起徜徉在校園中，我感到很幸福。不過為了這份幸福，我愛人也做出了很大的犧牲，無論是學術發展還是家庭事務方面，她都很遷就我。我現在能在這裡講得頭頭是道，背後其實都是她在默默付出。我非常感激她。

問：您的成果多次發表在STOC、FOCS、SODA等理論計算機的頂級會議。對於如何做出頂尖的理論計算機研究成果，能否介紹一些您的心得？

尹一通：能在這幾個理論計算機方向的頂級會議發表成果，的確都是非常困難的。可以說，就算是這個領域裡特別傑出的學者，也無法保證自己的下一個成果就能穩定可控地達到這個水平。因此，我也不敢說我能總結出什麼心得來。回過頭來看，一些引領後世的原創性成果，當初也是被這幾個會議拒了一圈，最後發表在了別的地方，而且這種事已經發生了多次。因此，對於理論計算機科學，哪怕只是算法與計算複雜性理論，最高水平的成果是否能被這幾個頂會完全代表，也是值得商榷的。

我工作之後做出的成果的確好於學生時代。我個人也能體會出來，自己每經歷一個階段，科研方面的功力都能得到一些提升。老去揣摩自己哪裡又變強了，這一做法可能有點不夠謙虛，但這也許是「人生不如意十之八九」的科研創新的荊棘之路上得之不易的正面反饋。我覺得我能夠有這樣持續的進步，首先和我們單位優越的學術環境以及單位和我之間的默契、互相信任密不可分。一直以來，我追求的目標就是成為一個更加優秀的學者，擁有更好的學問，而不是單純發表什麼檔次的論文。這一點，也算是理論計算機科學的傳統價值觀了，即追求深厚功力，而非赫赫戰績，高水平的科研產出只是好學問的體現之一。

為了追求更好的學問，我做過幾方面努力，感覺都挺有效的：一是做個好學生，一直學習新東西，打磨自己的技藝。二是做個好學徒，主動去和領域裡更厲害的同行合作，在這個過程中舉一反三地體會他們的深刻思想和創新思維。第三，也是常被忽視的一點，是努力做個厲害的老師。能把一個複雜且克服了一定難題的內容講清楚，首先在解決問題的思路上就要想得清晰透徹，對於解決問題的方法不僅要掌握而且還要能夠駕馭，這是一種好的思維能力和習慣；另外，教學也迫使我深入地思考什麼樣的內容是值得進入課堂的，這對研究品味也是一種很好的考驗和鍛鍊。做學生、做學徒、做老師，這些努力實則沒有一個是對科研產出直接「交差」的。我能夠在成長之路上獲得這些積累，而不僅僅是消耗，我非常感激我的工作單位南大計算機系，也很珍惜我和我所熱愛著的母校、母系之間的這種默契和互信。

問：能否介紹一下您如何判斷一個人是否適合從事理論計算機研究？另外，您還有什麼想對希望從事這個方向的學生說的？

尹一通：我其實不太認可「適合」這個概念，因為它背後透著一種對投入產出這筆「效益帳」的精打細算。理論計算機科學領域裡一個老前輩曾經表達過這樣的一個觀點：「當你開始問你自己適合不適合一件事的時候，你已經不適合了。」我並不完全同意他這個有點絕對的看法，畢竟人都難免有信念動搖的時候，但是我很理解他這個說法背後的緣由：對於每一個因感到自己不適合而離開這個方向的學生，都存在一個比他在客觀上更加不適合此方向，但卻最後留下來了的人，而且那個人有可能最終做得還不錯。我覺得最重要的還是對這個方向有足夠的熱愛和執著。應該確定的是，自己喜歡的是現實中真正的理論計算機科學，而不是腦海想像中的；是喜歡學習它、從事它、從根本上弄懂它，而不是只喜歡談論與它相關的新聞和感悟；是發自內心的喜歡，哪怕現在只是看著順眼的階段，也要做好遲早為這個「磨人的小妖精」辛苦付出、經歷挫敗、為伊消得人憔悴的思想準備。

理論計算機科學領域的一個挑戰是有過高的同行壓力(peer pressure)，尤其在年輕人之間，因為這個領域匯集了許多天才。在我國年輕一輩裡，就有畢業自清華姚班的陳立傑同學連續獲得STOC'19、FOCS'19最佳學生論文獎；今年還有北大圖靈班的吳克文同學獲得了STOC'20最佳論文獎，得獎時他本科都還沒畢業。面對如此強大的同行榜樣，我想對年輕學生囑咐一句：「Be inspired, not intimated!」——受到鼓舞與啟發，而不是被嚇倒！在學術的路途上，最不缺「山外有山，人外有人」這一課。即便是再優秀的人，也難免在年輕時感受到來自更加優秀的同輩帶來的壓力和隨之而來的挫敗感。而讀博士最重要的磨練之一，就是從這些優秀的事例中獲得鼓舞和啟發，不再感到挫敗，就像我們從那些偉大的研究成果以及人類科學的壯舉中獲得靈感一樣。陳立傑當年在清華特等獎學金評選時所發出的「我要成為一名理論計算機科學家！」的宣言，其中飽含的青春與熱血，讓我深受鼓舞。在此，我也借用他的這句宣言作為本次採訪的標題，因為這同時也是我的理想，也順便表達我對這個領域年輕有為的「後浪」們的致敬。

今年的STOC改為了線上舉辦，我是其中一個研習會(workshop)的研討專家(panelist)，可以看到所有聽眾的名單。其中中國人所佔的比例不小，這是近年來一個喜人的趨勢，隨著我國綜合國力的不斷增強，理論計算機科學這個基礎性方向裡的中國人也越來越多了。而且，從年齡結構上看，年輕群體的中國人比例越來越高，具體子領域的分布也越來越廣。我想，未來中國理論計算機科學的發展道路仍會充滿艱辛和曲折，但前景必然是光明的！

特別聲明：中國計算機學會(CCF)擁有《中國計算機學會通訊》(CCCF)所刊登內容的所有版權，未經CCF允許，不得轉載本刊文字及照片，否則被視為侵權。對於侵權行為，CCF將追究其法律責任

作者簡介

俞 揚

CCF高級會員、CCCF動態欄目編委。南京大學教授。主要研究方向為人工智慧、機器學習、演化學習。[e-mail]