E-Mail： ppeng@ustc.edu.cn
個人主頁：http://staff.ustc.edu.cn/~ppeng/
主要研究方向：理論計算機科學，圖算法、大數據算法的理論與應用
彭攀，中國科學技術大學計算機學院特任教授。2007年獲得北京師範大學數學學士學位。2013年獲得中國科學院軟件研究所博士學位。曾任中科院軟件所助理研究員，曾於德國多特蒙德工業大學、奧地利維也納大學做博士後，曾擔任英國謝菲爾德大學終身製講師（助理教授）。主要研究理論計算機科學，圖算法、大數據算法的理論及其（在機器學習、數據挖掘等領域的）應用。相關成果已發表在STOC、SODA、CCC、ICALP、COLT、KDD等一流國際會議上。多次受邀擔任國際知名會議(如LATIN、AAAI、IJCAI等)的程序委員會成員。曾受邀參加歐洲研究委員會(ERC)及以色列科學基金的項目評審工作。目前擔任Frontiers of Computer Science, International Journal of Software and Informatics等期刊的(青年)編委。
導師選題：
| 麵向圖數據流的學習增強算法研究 | 圖數據流算法用於處理不斷更新的圖數據，例如邊或頂點的插入和刪除。這些算法在有限的空間資源下高效地進行操作，並在處理完更新後，能夠回答關於輸入圖的各種性質或結構的查詢。這種算法非常適用於大規模和動態變化的圖數據，能夠在保持高效性的同時，適應不斷變化的輸入。
本項目專注於基於預測模型的圖數據流算法，這種算法也被稱為學習增強算法。我們假設算法能夠獲得關於未來更新的不完美預測，探討如何利用這些預測來優化算法的空間效率和近似比之間的權衡。具體來說，我們將研究如何通過利用這些預測信息來減少所需的存儲空間，同時保持對圖數據的準確近似和高效查詢能力。
在本項目中，我們的主要目標是設計和分析用於動態圖數據流中跨度圖（spanner）構造的學習增強算法。給定一個圖G，跨度圖是其一個稀疏的子圖，它在某種程度上保留了G 中最短路徑的長度。傳統的數據流模型中，構建具有最優大小和近似比的跨度圖是一項極具挑戰性的任務，因為它需要在有限的空間和時間內處理動態變化的圖數據。
我們希望通過結合學習預測的方法，突破這些傳統方法的限製，實現更高效的跨度圖構造。具體來說，本項目將探索如何設計能夠利用預測信息的算法，以提高跨度圖構造的效率和精度，從而在處理大規模動態圖數據時，既能夠有效地管理存儲空間，又能夠在近似比上達到較好的效果。我們的研究將對圖數據流領域中的算法設計和優化提供重要的理論支持和實踐指導。
參考文獻：
https://arxiv.org/pdf/2204.12055
https://arxiv.org/pdf/2007.14204 | | 麵向Friedkin–Johnsen模型的意見估計算法研究 | 在線社交網絡已經成為現代社會的重要組成部分，這些網絡中的討論在很大程度上塑造了人們對政治、疫苗接種等多樣話題的觀點。為了理解和分析這種意見形成的複雜過程，Friedkin–Johnsen (FJ) 模型被廣泛應用於描述網絡中的意見傳播和形成機製。該模型不僅能夠捕捉網絡中意見的極化和分歧，還提供了量化這些現象的度量標準。
本項目旨在針對FJ模型中的節點意見及相關度量（如極化和分歧）研究高效的算法，特別是開發能夠在亞線性時間內近似這些度量的算法。這些算法的設計目標是能夠從大規模網絡中僅讀取部分圖信息，從而顯著提高計算效率。通過優化算法的性能，我們希望能夠在實際應用中更快地得到網絡中節點意見的準確近似值，進而更有效地評估和理解網絡中的意見動態。我們的研究將深入探索如何利用部分數據進行高效計算，以及在麵對大規模和動態變化的社交網絡時，如何在保持高準確度的同時降低計算複雜度。
參考文獻：https://arxiv.org/pdf/2404.16464 | | 平麵圖性性質檢測算法的下界研究 | 平麵圖性是一種重要的圖性質，它指的是包含所有平麵圖的圖的集合。平麵圖，即能夠在平麵上繪製而不產生邊交叉的圖，具有許多應用和理論意義。在計算機科學和圖論中，平麵圖性不僅涉及圖的表示和處理，還與許多實際問題密切相關，如電路設計、網絡布局和地理信息係統。
近期，研究者在平麵圖性檢測問題上取得了顯著進展，提出了首個針對度數受限圖的平麵圖性亞線性檢測算法。該算法的查詢複雜度是關於親近性參數 $\varepsilon$ 的多項式，這一突破為解決大規模圖的平麵圖性檢測提供了新的思路。然而，盡管取得了這些進展，對於該問題的複雜性仍有許多未知之處。
本項目旨在從計算複雜性的角度深入研究平麵圖性性質檢測算法的查詢複雜度。具體而言，我們計劃證明平麵圖性性質檢測算法的查詢複雜度下界，即探索在最壞情況下，任何算法在處理平麵圖性檢測問題時所需的最低查詢複雜度。這一研究不僅有助於揭示平麵圖性檢測的內在難度，也將為未來算法設計提供理論指導，並可能推動相關領域的進一步發展。
參考文獻：
https://www.wisdom.weizmann.ac.il/~oded/PDF/pt-v3.pdf (第9章)
https://arxiv.org/abs/1904.01055 |
|
