Email: shao10@ustc.edu.cn
個人主頁：http://staff.ustc.edu.cn/~wwwucuc/
主要研究方向：理論計算機科學及其與統計物理、量子理論的交叉方向
邵帥，bet188app
特任教授、博士生導師。2014年本科畢業於188金宝慱体育版
少年班學院華羅庚班，2020年博士畢業於威斯康星大學麥迪遜分校計算機係，就讀期間還曾獲數學碩士及計算機碩士學位。之後分別在牛津大學及愛丁堡大學從事博士後工作，在牛津工作期間同時被選為Wolfson學院初級研究員。主要研究領域為理論計算機科學，同時涉及其與統計物理、量⼦理論的交叉⽅向。近年來，在精確計數的複雜度分類，近似計數算法與相變現象，量⼦糾纏態等價類分類等⽅⾯取得了一定研究成果，在領域權威期刊和頂級國際會議上發表多篇論文。
導師選題：
| 邊約束滿足問題的計算複雜性分類研究 | 能在多項式時間內能驗證解的正確性的判定問題稱作NP問題，能在多項式時間內求解的判定問題稱作P問題。NP問題是否都是P問題？這便是千禧年七大數學難題之一：P vs NP。該問題也是理論計算機科學領域內的著名難題。 P vs NP是針對判定問題而言的。判定問題可以自然地推廣到計數問題（計算解的個數）。每個NP問題都有其對應的計數版本，這些問題構成集合#P。FP指的是#P中可在多項式時間內求解的問題。FP vs #P（即是否#P類中的每個計數問題都可在多項式時間內求解）同樣是理論計算機科學中一個十分重要的根本問題。大多數研究者相信P≠NP或FP≠#P。在此假設下，著名的Ladner定理表明：存在既不是P也不是NPC的NP問題。然而人們發現，對於某個問題框架下所有的判定或計數問題，其計算複雜性要麼是最簡單的（P或FP），要麼是最難的（NP難或者#P難），不存在中間地帶。目前研究者們不斷地對包含問題越來越廣泛的問題框架證明計算複雜性二分定理，進而探索使這類二分定理成立的問題框架的“極限”在哪裏。這其中最為廣泛研究，成果也最為矚目的問題框架便是約束滿足問題（Constraint Satisfaction Problem, CSP）。約束滿足問題（CSP）廣泛來源於邏輯學、組合學、物理學等領域。它是SAT問題的自然推廣，同時包含了諸如獨立集、地圖染色等諸多有著廣泛應用的基礎問題。CSP問題的計數版本稱作#CSP。目前，對於CSP和#CSP，完備的計算複雜性二分定理均已被證明。然而CSP框架仍有一定局限，很多非常基礎的著名問題並不能被CSP框架所涵蓋，這其中最為典型的例子就是圖的完美匹配問題。判定圖是否存在完美匹配可被著名的Edmonds’Blossom算法解決；其在一般圖上的計數問題，是第一個被證明的#P完全問題；而其在平麵圖上的計數問題，則可被統計物理中著名的FKT算法在多項式時間內解決。因為圖的匹配問題蘊含著這些如此不平凡的算法和深刻的計算複雜性結果，其重要性不言而喻。本課題將致力於研究一類比CSP問題更加廣泛的問題框架邊約束滿足問題（Edge Constraint Satisfaction Problem, Edge-CSP），並探索其在判定、優化及計數問題下的計算複雜性分類。 |
|
