我們的研究⽅向是理論計算機科學(Theoretical Computer Science)。理論計算機科學是計算機科學的理論根基，旨在使⽤數學⼯具探索計算的本質與界限，並為計算機專業問題找到嚴格的、具有思維創新性的解。
我們的具體研究⽅向包括：
（⼀） 現代算法理論——發展現代的算法理論⼯具為前沿算法問題給出更好、更聰明的算法上界，例如隨機算法、近似算法、採樣與計數算法、並⾏與分布式算法等；
（⼆）複雜性下界——克服複雜性理論中的根本障礙從⽽為基礎性難題證明其計算難度的下界，例如數據結構複雜性、通信複雜性、分布式計算下界等。
本研究組是中國⼤陸⽬前為數不多的在理論計算機科學這⼀計算機科學最根本的⽅向上持續做出世界⼀流科研成果的研究組之⼀。研究組⽬前已在理論計算機科學的⼀流國際會議FOCS、SODA、ICALP、PODC、SPAA、RANDOM、CCS發表論⽂⼆⼗餘篇。論⽂獲得來⾃UC Berkeley、Stanford、Princeton、Columbia、Oxford、EPFL、以⾊列Weizmann科學院等國際著名單位包括數位哥德爾獎（Gödel Prize）得主、富爾克森獎（Fulkerson Prize）得主、狄克斯特拉獎（Dijkstra Prize）得主、歐洲科學院院⼠在內的國際權威學者的引⽤。並獲得並⾏算法領域頂級會議SPAA 2016優秀論⽂（outstanding paper）獎，是該著名會議創⽴28年來，來⾃中國⼤陸的論⽂⾸次獲獎。
尹⼀通：教授、博⼠⽣導師。2009年博⼠畢業於耶魯⼤學。研究⽅向為理論計算機科學。微軟亞洲研究院「鑄星學者」，⼊選教育部新世紀優秀⼈才，獲中創軟體⼈才獎。多次受邀在龐加萊數學所、加州⼤學伯克利分校、算法隨機性中⼼等國際著名學術單位作⼀⼩時報告。並於2016年受邀作為計數算法全球50位權威學者之⼀參加UC Berkeley舉辦的「計數複雜性與相變」國際項⽬。
個⼈主頁：http://tcs.nju.edu.cn/yinyt/
鄭朝棟：助理研究員。2015年博⼠畢業於新加坡國⽴⼤學，2016年在德國弗萊堡⼤學從事博⼠後研究⼯作。博⼠與博⼠後導師分別是分布式計算理論的國際著名學者Seth Gilbert和Fabian Kuhn。2017年加⼊南京⼤學計算機科學與技術系。研究⽅向為分布式計算理論，⽬前主要研究領域為⽆線⽹絡中的分布式算法理論。
個⼈主頁：https://chaodong.me/
我們歡迎對計算機科學的理論有興趣和熱情，接受過良好的數學訓練並具有⼀定數學成熟度，願意迎接思維挑戰、勇於克服困難、做事認真且持之以恆的同學加⼊！
同學們可發送個⼈簡歷和⾃我介紹⾄郵箱：yinyt@nju.edu.cn，與尹⼀通教授聯繫。
科研成果展示
所謂超圖，它與普通圖的區別在於它的⼀條超邊可以關聯多個頂點。超圖中的⼀個匹配即是⼀個超邊的集合，其中任意兩條超邊不共享頂點。我們考慮的問題即是如何近似計算所有匹配的權重和。該問題是組合數學、計數複雜性、統計物理領域的著名難題。
在⽆窮正則、⼀致超樹的匹配模型上，Gibbs測度的唯⼀性會在活動性參數的某⼀閾值處發⽣突變。在閾值之下，Gibbs測度是唯⼀的，同時相關性衰減性質成⽴。在閾值之上，Gibbs測度不唯⼀，同時相距很遠的兩點相關性依然很⼤。
在活動性參數⼩於閾值時，我們利⽤相關性衰減性質，對所有度受限的超圖找到了⼀個⾼效算法近似計算該圖的配分函數。同時，我們證明了在活動性參數約⼤於兩倍閾值時，不存在⾼效的近似算法，除非NP=RP。
學生作者：
宋仁傑：15級碩⼠⽣，國家獎學⾦獲得者
趙⾦滿：11級本科⽣，⽬前在威斯康星⼤學攻讀博⼠
論⽂發表於隨機算法領域著名國際會議RANDOM 2016。
採樣是指在特定的概率分布中，隨機取出⼀個樣本，它在理論計算機，統計物理，機器學習等領域有著⼗分⼴泛的應⽤。當概率分布變得複雜時，採樣不再是⼀項簡單的任務，例如：等概率採樣圖G(V,E)上的⼀種合法染⾊。
傳統的採樣算法⼤多數為串⾏算法，具體到採樣染⾊問題上：每⼀步隨機選擇⼀個點，隨機修改選中點的顏⾊。我們提出了分布式採樣算法：每⼀步隨機修改「很多」點的顏⾊，提⾼效率的同時依然能保證正確的概率分布。
我們不但提出了算法，也證明了所有分布式算法解決此類採樣問題的理論下界——⾄少要計算多少輪，才能保證算法得到預期的概率分布。
學生作者：
鳳維明：16級直博⽣
孫宇鑫：13級本科⽣，即將赴威斯康星⼤學攻博士
論⽂發表於分布式計算理論國際頂級會議PODC 2017。
給定d維漢明空間中的n個點，要求構造⼀個數據結構，使得任意詢問d維漢明空間中的⼀個點q，我們都能快速地回答這個n個數據點中哪個點到點q的漢明距離最近，這就是漢明空間中的最近鄰搜索問題。最近鄰搜索問題是諸多數據結構問題中⾮常重要⽽又基本的問題，在多個領域都有⾮常重要的應⽤。
該問題飽受維數災難（curse of dimensionality）的困擾：即複雜度隨空間的維數d呈指數級增長。另⼀⽅⾯，在摩爾定律逐漸失效的今天，並⾏計算是我們突破時間瓶頸的新⽅向。
圖靈獎得主姚期智提出的單元偵測模型(Cell-Probe Model)是我們研究數據結構問題的重要理論模型。在該模型中，空間複雜度被表⽰為⽤於存儲數據的內存單元的數量，⽽時間複雜度則被精簡的表⽰為算法回答⼀個查詢所查看的內存單元的數量。
我們運⽤隨機算法對最近鄰搜索問題進⾏近似求解，以打破維數災難；考慮並⾏化的單元偵測模型以研究並⾏化的隨機算法，最終給出兩個近似最近鄰搜索問題的並⾏隨機算法。並⾏算法的時間複雜度有計算的輪次k和計算的花費t兩個維度。運⽤來⾃通訊複雜性的下界證明技術，我們證明我們的算法在特定情景下達到了最優。
學生作者：
劉明謀：15級碩⼠⽣，國家獎學⾦獲得者
潘笑吟：13級本科⽣，已保研，即將在南⼤計算機系理論組攻讀碩⼠
論⽂發表於並⾏算法領域國際頂級會議SPAA 2016。
認知⽆線電⽹絡是⼀種新型⽆線⽹絡。此類⽹絡中，不同節點可依據⾃⾝所處的⽹絡環境選擇不同的信道，且同⼀節點可使⽤的信道也會隨外部⽹絡環境的變化⽽動態調整。這種⾼度的不確定性與動態性可以幫助認知⽆線電⽹絡充分利⽤有限的頻譜資源，提⾼⽆線通信的效率。然⽽，這些特性也使得在認知⽆線電⽹絡中設計與分析分布式算法變得極為困難。
本項⽬中，我們針對鄰居發現、⼴播、聚合等基礎⽹絡功能的實現問題，提出了⼀系列隨機算法，形式化的證明了算法的正確性，並給出了算法的複雜度上界。此外，通過分析解決相關問題的複雜度下界，也證明了在很多情況下我們所提出的算法的性能已經接近或達到。
(漸進)最優。
在算法的設計與分析、複雜度下界的證明過程中，我們使⽤了⼀系列分布式計算理論中常見的技術與技巧，體現了理論計算機科學研究對實際應⽤場景的指導作⽤。例如，使⽤分布式點著⾊與邊著⾊算法提⾼⼴播的效率，使⽤猜測⼆分圖匹配問題的複雜度下界來分析鄰居發現與⼴播問題的複雜度下界，等等。
作者：
Seth Gilbert, Fabian Kuhn, Calvin Newport, 鄭朝棟
論⽂發表於分布式計算理論國際頂級會議PODC 2015、PODC 2017。