[08-26] 約束滿足解的近線性時間采樣算法----中國科學院軟件研究所

[08-26] 約束滿足解的近線性時間采樣算法

文章來源： | 發布時間：2022-08-22 | 【打印】【關閉】

Title:約束滿足解的近線性時間采樣算法

Speaker:尹一通（教授，南京大學）

Time:8月26日（周五）10:00-12:00

Venue:線上：騰訊會議 860-289-398

Abstract:約束滿足問題 (constraint satisfaction problem, CSP) 是計算機科學關注的一類基本的計算問題。例如經典的可滿足性判定 (SAT) 問題即是約束滿足問題的一個特例。本次講座將介紹約束滿足解的快速采樣算法。該系列算法在類似洛華茲局部引理（Lovász Local Lemma）的條件下，可在近線性時間內輸出接近均勻分布的約束滿足解。

Bio:尹一通，本科與博士先后畢業于南京大學和耶魯大學，目前為南京大學教授，研究方向是理論計算機科學，具體方向為采樣算法、大數據計算理論等。在 JACM、SICOMP、STOC、FOCS、SODA等理論計算機科學期刊與會議發表論文四十余篇。主持國家重點研發計劃項目，獲得國家自然科學基金優青、CCF-IEEE CS青年科學家等，指導博士生獲CCF優秀博士學位論文獎。