# Combinatorial Bernoulli Factories with Polynomially Many Coins

**Authors:** Renato Paes Leme, Rad Niazadeh  
**Published:** 12 Nov 2026  
**Links:** [arXiv](https://arxiv.org/abs/2611.17223) · [PDF](https://arxiv.org/pdf/2611.17223) · [This page](https://omen-bit.github.io/ai-paper-daily/paper/2611.17223.html)

## 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/δ_*, 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$.

---

Notes written by AI from the paper, numbers copied from the abstract. Check the paper before you rely on them. From AI Papers Daily.