亚星国际正网

[08-26] 约束满足解的近线性时间采样算法

文章来源:  |  发布时间:2022-08-22  |  【打印】 【关闭

  

Title:约束满足解的近线性时间采样算法

Speaker:尹一通(教授,南京大学)

Time:826日(周五)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优秀博士学位论文奖。 
亚星国际正网(大理)有限公司