4 citations · 7 across the 7 of their papers we have counts for
Showing 2022Show all
3 papers · 1 filter
cs.DS2022
Deterministic counting Lovász local lemma beyond linear programming
Kun He, Chunyang Wang, Yitong Yin
We give a simple combinatorial algorithm to deterministically approximately count the number of satisfying assignments of general constraint satisfaction problems (CSPs). Suppose t…
cs.DS2022
Improved Bounds for Sampling Solutions of Random CNF Formulas
Kun He, Kewen Wu, Kuan Yang
Let be a random -CNF formula on variables and clauses, where each clause is a disjunction of literals chosen independently and uniformly. Our goal is to sample a…
cs.DS2022
Sampling Lovász Local Lemma For General Constraint Satisfaction Solutions In Near-Linear Time
Kun He, Chunyang Wang, Yitong Yin
We give a fast algorithm for sampling uniform solutions of general constraint satisfaction problems (CSPs) in a local lemma regime. Suppose that the CSP has variables with doma…