{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-12","reactions":{}}