{"arxiv_id":"2611.17223","title":"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 $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/{\\delta_*}$, where ${\\delta_*}=\\min_i\\{x_i,1-x_i\\}$ is never supplied to the algorithm. For perfect matchings this gives $O(n^{8}{\\delta_*}^{-2}\\log(n/{\\delta_*}))$ 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$.","primary_cat":"cs.DS","cross_cats":["cs.GT","cs.LG","math.PR","stat.CO"],"submitted_at":"2026-11-12T18:19:37+00:00","latest_version":1,"source":"arxiv","source_label":"arXiv","source_url":null,"has_pdf":true,"has_source":false,"verdict":"ACCEPT","confidence":"HIGH","one_line_summary":"A polynomial-time combinatorial Bernoulli factory for every affine slice of the cube, with expected coin flips polynomial in dimension and 1/δ* (the minimum distance to the cube boundary), without knowing δ*.","novelty_score":8.0,"correctness_risk":"low","formal_verification":"partial","upvotes":0,"downvotes":0,"pith_score":0,"inbound_count":0,"_links":{"html":"https://pith.science/paper/2611.17223","verdict":"/api/v1/verdicts/2611.17223"}}