机器学习实验室博士生系列论坛（第二十期）——Sample constraint satisfaction solutions
报告人：Guangzeng Xie(PKU)
时间：2021-12-08 15:10-16:10
地点：北大理科一号楼1513会议室 & 腾讯会议 761 4699 1810
Abstract:
The space of constraint satisfaction solutions is one of the most well-studied subjects in Computer Science.
Given a collection of constraints (or clauses) defined on a set of variables, each clause contains k Boolean variables and each variable appears in at most d clauses, a solution to the constraint satisfaction problem (CSP) is an assignment of variables such that all constraints are satisfied.
When k \gtrsim log d, Lovasz Local Lemma shows that there must exist a solution and algorithmic LLL, developed by Moser and Tardos, ensured that a solution can be constructed in polynomial time.
A more challenging problem raised then: how to sample a solution of CSP.
The disconnected solution space, via local updates of variables, even when the existence of solutions is guaranteed by the local lemma, is the major difficulty for efficiently sampling.
In this talk, we will review recent works that trying to bypass such connectivity barrier.
