Sampling constraint satisfaction solutions in the local lemma regime (Kun He)

Abstract

The space of constraint satisfaction solutions is one of the most well-studied subjects in Computer Science. Given a collection of constraints defined on a set of variables, a solution to the constraint satisfaction problem (CSP) is an assignment of variables such that all constraints are satisfied. A fundamental criterion for the existence of constraint satisfaction solutions is given by the Lovasz local lemma (LLL). Interpreting the space of all assignment as a probability space and the violation of each constraint as a bad event, the local lemma characterizes a regime within which a constraint satisfaction solution always exists, by the tradeoff between: (1) the chance for the occurrence of each bad event and (2) the degree of dependency between them. In Computer Science, the studies of the Lovasz local lemma are more focused on the algorithmic LLL, which is concerned with not just existence of a constraint satisfaction solution, but also how to find such a solution efficiently.

In this talk, we are concerned with a problem that we call the sampling LLL, which asks for the regimes in which a nearly uniform satisfaction solution can be generated efficiently. We will summary the new progresses and propose some open challenges.

Time

2022-08-29  13:30 - 14:30   

Speaker

Kun He,  Institute of Computing Technology, Chinese Academy of Sciences

Room

Tencent meeting ID: 971783093; PW: 123456