AbstractSampling a target distribution with an unknown normalization constant is a fundamental problem in computational science and engineering. Often, dynamical systems of probability densities are constructed to address this task, including MCMC and sequential Monte Carlo. Recently, gradient flows in the space of probability measures have been increasingly popular to generate this dynamical s...
AbstractLet Φ 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.'2...