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. 

Time

2023-06-17  15:00 - 15:30   

Speaker

Kuan Yang, Shanghai Jiao Tong University

Room

Guangdong Hotel