[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）的条件下，可在近线性时间内输出接近均匀分布的约束满足解。
