[08-亚博88体育

[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优秀博士学位论文奖。