Lab Lunch: 10 March 2020 - Heng Guo

Title:  Markov chain algorithms for bounded degree k-Sat

Abstract:

I will present a Markov chain based algorithm to sample satisfying assignment of k-Sat, where each variable appears in sufficiently few (but still exponential in k) clauses. The solution space for this problem is not connected via single variable updates, and we bypass this issue by defining a suitable projection of the desired distribution and running Markov chains over it.

Joint work with Weiming Feng, Yitong Yin, and Chihao Zhang