← All papers
First page of Combinatorial Bernoulli Factories with Polynomially Many Coins

Combinatorial Bernoulli Factories with Polynomially Many Coins

Renato Paes Leme, Rad Niazadeh

cs.DS Nov 12, 2026 · v1 cs.GT cs.LG math.PR stat.CO
The paper's results on efficient combinatorial Bernoulli factories were formalized in Lean 4, with a public GitHub repository.
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$.

Combinatorial Bernoulli factories turn coins of unknown biases x into a random vertex of a polytope P whose mean is exactly x. The prior factory of Niazadeh, Paes Leme, and Schneider is very slow: on the Birkhoff polytope it uses at least n^{2n-1} flips in expectation.

Flip every coin in batches, take the empirical mean, and project it orthogonally onto the affine hull of P, which preserves unbiasedness exactly. If the projected point is feasible, round it to a vertex. If it is infeasible (a rare event), round a known interior point instead and keep the residual rather than discarding the sample. For affine slices of the cube, a pilot estimate of the margin δ* = min_i{x_i, 1-x_i} replaces any supplied promise. The results were formalized in Lean 4.

For every affine slice of the cube, a single algorithm is given whose expected coin flips and running time are polynomial in the dimension and 1/δ*, without δ* being supplied. For perfect matchings this gives O(n^8 δ*^{-2} log(n/δ*)) flips. For general polytopes, exact rounding is achieved given a point deep inside P and a promised margin for x.