Id: arxiv/2611.17223 Url: https://arxiv.org/abs/2611.17223 Tags: cs.DS, cs.GT, cs.LG, math.PR, stat.CO Score: 0 Title: Combinatorial Bernoulli Factories with Polynomially Many Coins Domain: cs.DS Source: arxiv Authors: Renato Paes Leme, Rad Niazadeh Reviews: 0 Subject: cs.DS Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Discussed: 0 Published: 2026-11-12 Page: https://delphi.science/r/arxiv/2611.17223 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…