2 papers
cs.CC2025
Generating uniform linear extensions using few random bits
Mark Huber
A \emph{linear extension} of a partial order \(\preceq\) over items \(A = \{ 1, 2, \ldots, n \}\) is a permutation \(Ï\) such that for all \(i < j\) in \(A\), it holds that \(\neg…
cs.DS2024
Optimal rolling of fair dice using fair coins
Mark Huber, Danny Vargas
In 1976, Knuth and Yao presented an algorithm for sampling from a finite distribution using flips of a fair coin that on average used the optimal number of flips. Here we show how…