Combinatorial Bernoulli Factories with Polynomially Many Coins

We provide an efficient implementation of combinatorial Bernoulli factories. Such a factory turns coins of unknown biases $x$ into a random vertex of a polytope $P$ whose mean is exactly $x$. For every affine slice of the cube (the class of polytopes that admit a factory), we give a single algorithm whose expected number of coin flips and running time at every interior $x$ are polynomial in the dimension and in 1/δ_*, where δ_*=\min_i\x_i,1-x_i\ is never supplied to the algorithm. For perfect matchings this gives O(n^8δ_*^-2\log(n/δ_*)) flips, while the factory of Niazadeh, Paes Leme, and Schneider [STOC 2021] spends at least n^2n-1 flips in expectation at the uniform doubly stochastic matrix. For other polytopes, our method rounds exactly given a point deep inside $P$ and the promise that $x$ is far from the boundary of $P$.