Improved Bounds for Sampling Solutions of Random CNF Formulas

Abstract

Let Φ be a random k-CNF formula on n variables and m clauses, where each clause is a disjunction of k literals chosen independently and uniformly. Our goal is, for most Φ, to (approximately) uniformly sample from its solution space.

Let α=m/n be the density. The previous best algorithm runs in time n^poly(k,α) for any α≲2^(k/300) [Galanis, Goldberg, Guo, and Yang, SIAM J. Comput.'21]. In contrast, our algorithm runs in near-linear time for any α≲2^(k/3). This work was published in SODA'23.

About the speaker

I am an assistant professor in the John Hopcroft Center for Computer Science at Shanghai Jiao Tong University.

I was awarded the Ph.D. degree in Computer Science by the University of Oxford in 2020, where I was supervised by Prof. Leslie Ann Goldberg and Prof. Andreas Galanis. I was a member of St. Hugh's College at Oxford, and also a Clarendon scholar, fully-funded by the Clarendon Scholarship from 2015 to 2019. Before coming to Oxford, I obtained my bachelor degree in Computer Science from Zhiyuan College at Shanghai Jiao Tong University in China.

I am interested in many aspects of theoretical computer science, discrete probability and combinatorics. Currently I mainly work on designing and analysing approximation algorithms for counting and sampling problems.