Sampling permutations satisfying constraints within the lopsided local lemma regime

Kun He, Guoliang Qiu, Xiaoming Sun

Sampling a random permutation with restricted positions, or equivalently approximating the permanent of a 0-1 matrix, is a fundamental problem in computer science, with several not…