Generating uniform linear extensions using few random bits

A \emph{linear extension} of a partial order $⪯$ over items $A=\{1,2,\dots ,n\}$ is a permutation $\sigma$ such that for all $i<j$ in $A$, it holds that $\mathrm{\neg }(\sigma (j)⪯\sigma (i))$. Consider the problem of generating uniformly from the set of linear extensions of a partial order. The best method currently known uses $O(n^3\ln (n))$ operations and $O(n^3\ln (n{)}^2)$ iid fair random bits to generate such a permutation. This paper presents a method that generates a uniform linear extension using only $2.75n^3\ln (n)$ operations and $1.83n^3\ln (n)$ iid fair bits on average.