WorksComputer Science
Combinatorial Bernoulli Factories with Polynomially Many Coins
Abstract
We provide an efficient implementation of combinatorial Bernoulli factories. Such a factory turns coins of unknown biases into a random vertex of a polytope whose mean is exactly . 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 are polynomial in the dimension and in , where is never supplied to the algorithm. For perfect matchings this gives flips, while the factory of Niazadeh, Paes Leme, and Schneider [STOC 2021] spends at least flips in expectation at the uniform doubly stochastic matrix. For other polytopes, our method rounds exactly given a point deep inside and the promise that is far from the boundary of .