【2022-08-26】SKLCS Seminar on”约束满足解的近线性时间采样算法”
| 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优秀博士学位论文奖。 |