Sampling permutations satisfying conjunctive constraints in the local lemma regime
何昆，4 月 14 日 11:00
Sampling permutations satisfying conjunctive constraints (PCC) is a fundamental problem in computer science. Many critical problems are only special cases of PCC, including the \(k\)-SAT, the hypergraph coloring, and the perfect matchings in bipartite graphs. We give a Markov chain based algorithm for sampling almost uniform solutions of PCC. Our sampling algorithm is accurate in a local lemma regime, and the running time is a fixed polynomial in both \(n\) and \(\Delta\), where \(n\) is the number of variables and \(\Delta\) is the maximum degree of the lopsidependency graph.
Previously, the sampling LLL only exists for the variable model, where the underlying probability space is a product space. For the sampling problem of PCC, the main challenge is that the underlying probability space is a joint space where the random variables in each permutation are not mutually independent. This leads to a long range correlation between the random variables of large permutations.